Авторефераты по всем темам >> Авторефераты по техническим специальностям

На правах рукописи

ЕГОРОВ СЕРГЕЙ ИВАНОВИЧ

МЕТОДЫ, АЛГОРИТМЫ И УСТРОЙСТВА КОРРЕКЦИИ АДДИТИВНЫХ И СИНХРОНИЗАЦИОННЫХ ОШИБОК ВО ВНЕШНИХ ЗАПОМИНАЮЩИХ УСТРОЙСТВАХ ЭВМ

Специальность 05.13.05 Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических наук

КУРСК 2009

Работа выполнена в ГОУ ВПО Курский государственный технический университет на кафедре вычислительной техники в совместной научноисследовательской лаборатории Центра информационных технологий в проектировании РАН и Курского государственного технического университета Информационные распознающие телекоммуникационные интеллектуальные системы.

Научный консультант: доктор технических наук, профессор, заслуженный деятель науки РФ Титов Виталий Семенович

Официальные оппоненты:

доктор технических наук, профессор, заслуженный деятель науки РФ Бурковский Виктор Леонидович доктор технических наук, Левин Илья Израилевич доктор технических наук, профессор, заслуженный деятель науки РФ Сизов Александр Семенович

Ведущая организация:

Московский технический университет связи и информатики

Защита состоится 24 декабря 2009 г. в 14 часов на заседании диссертационного совета Д 212.105.02 при Курском государственном техническом университете (305040, г. Курск, ул. 50 лет Октября, 94, конференц-зал).

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан л___ _________ 2009 г.

Отзывы на автореферат в двух экземплярах, заверенные печатью, просьба направлять по адресу: 305040, г. Курск, ул. 50 лет Октября, 94, ученому секретарю диссертационного совета Д 212.105.02.

Ученый секретарь диссертационного совета кандидат техн. наук, доцент Титенко Е.А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Современные информационные технологии, являющиеся двигателем общественного прогресса, основываются на применении электронных вычислительных машин: персональных ЭВМ, кластеров и сетей ЭВМ, суперЭВМ. Эффективность применения ЭВМ во многом определяется используемыми внешними запоминающими устройствами (ВЗУ). Хранение данных в ВЗУ ЭВМ с высокой плотностью и надежностью невозможно без использования помехоустойчивого кодирования.

Теория помехоустойчивого кодирования достаточно хорошо разработана. Большой вклад в эту область знания внесли работы как зарубежных ученых: К. Шеннона, Р. Хемминга, Р. Галлагера, Ф.Дж. МакВильямс, Р. Блейхута, C. Berrou и A. Glavieux, D.J.C. MacKay, так и российских: Э.Л. Блоха, В.В. Зяблова, Э.М. Габидуллина, К.Ш. Зигангирова, Е.А. Крука, В.В. Золотарева. К настоящему времени предложены и исследованы различные классы помехоустойчивых кодов, среди которых наибольшее распространение в ВЗУ ЭВМ получили коды Рида-Соломона.

Исследования в области алгоритмов декодирования, осуществленные У. Питерсоном, Э.Р. Берлекэмпом, Дж. Месси, Р. Блейхутом, Д. Форни, Y. Sugiyama, T.K. Truong, В.Б. Афанасьевым, позволили в основном решить задачу разработки декодеров кодов Рида-Соломона в микроэлектронном исполнении для исправления аддитивных ошибок в каналах передачи и хранения данных в 80-90-е годы 20-го века. Особенности коррекции ошибок во внешних запоминающих устройствах с использованием кодов РидаСоломона отражены в работах A.M. Patel, N. Glover, А.П. Типикина, Б.А. Савельева и др.

Однако коррекция ошибок, возникающих в канала х записи/воспроизведения ВЗУ, в настоящее время осуществляется недостаточно эффективно как с точки зрения достижения максимальной степени повышения достоверности считываемых с носителя данных, так и с точки зрения оптимальности ее аппаратной реализации.

Недостаточно высокая степень повышения достоверности считываемых данных определяется тем, что потенциальные корректирующие способности кодов Рида-Соломона в ВЗУ ЭВМ используются не полностью:

число исправляемых ошибок в кодовом слове ограничивается половиной минимального кодового расстояния, недостаточно точно локализуются ошибки синхронизации, не полностью используются возможности кодовых конструкций для исправления ошибок синхронизации.

Известные алгоритмы декодирования кодов Рида-Соломона (Guruswami-Sudan, Koetter-Vardy Parvaresh-Vardy,), позволяющие исправлять ошибки за границей половины минимального расстояния кода, пока не реализованы в устройствах коррекции ошибок ВЗУ ЭВМ из-за высокой вычислительной сложности. Известные методы исправления ошибок синхронизации с использованием специального кодирования либо не учитывают характер ошибок в каналах воспроизведения ВЗУ (M. Davey), либо требуют внесения слишком большой избыточности (P. Bours) и также не нашли применения в устройствах коррекции ошибок ВЗУ.

Таким образом, в настоящее время существует проблемная ситуация между объективной необ ходимостью повышения достоверности считывания данных с носителя без уменьшения его полезной емкости и отсутствием методов, алгоритмов и устройств коррекции ошибок, решающих эту задачу с приемлемой аппаратной сложностью.

В связи с вышеизложенным актуальной является научно-техническая проблема повышения эффективности коррекции ошибок, возникающих в каналах записи/воспроизведения внешних запоминающих устройств ЭВМ.

Теоретический аспект сформулированной проблемы заключается:

- в развитии математического базиса процедур эффективной коррекции аддитивных и синхронизационных ошибок:

- в создании методов и алгоритмов декодирования кодов РидаСоломона за границей половины минимального кодового расстояния;

- в создании методов и алгоритмов коррекции ошибок синхронизации, учитывающих специфику ошибок, возникающих в каналах записи/воспроизведения ВЗУ;

- в разработке математического базиса синтеза устройств коррекции ошибок, обеспечивающих эффективное исправление ошибок.

Практический аспект проблемы состоит в создании устройств исправления ошибок, обеспечивающих эффективную коррекцию ошибок, возникающих в каналах записи/воспроизведения внешних запоминающих устройств ЭВМ, и имеющих допустимую для современной микроэлектроники аппаратную сложность. Применение этих устройств в ВЗУ ЭВМ позволит значительно повысить качество хранения в них данных.

Ключевые компоненты устройств коррекции ошибок, например, декодеры кодов Рида-Соломона могут быть использованы для повышения эффективности коррекции ошибок в каналах систем передачи данных.

Цель работы - создание теоретических и реализационных основ построения устройств коррекции ошибок, повышающих эффективность коррекции ошибок во внешних запоминающих устройствах ЭВМ.

В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:

1. Анализ состояния проблемы коррекции ошибок, возникающих в канале записи/воспроизведения данных ВЗУ и разработка структурной модели информационного канала ВЗУ.

2. Развитие теоретических основ декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния.

3. Разработка методов и алгоритмов декодирования кодов РидаСоломона, обеспечивающих:

- исправление ошибок за границей половины минимального кодового расстояния;

- декодирование кодов Рида-Соломона с минимальной задержкой на основе неполного вылавливания ошибок в кодовом слове.

4. Разработка методов, алгоритмов и устройств коррекции ошибок синхронизации путем использования М-последовательности.

5. Синтез структурных и функциональных схем устройств коррекции ошибок.

Объект исследования: средства коррекции ошибок, возникающих в каналах записи/воспроизведения внешних запоминающих устройств ЭВМ.

Предмет исследования: методы, модели, алгоритмы функционирования и структурно-функциональная организация устройств коррекции аддитивных и синхронизационных ошибок, использующих помехоустойчивые коды Рида-Соломона.

Методы исследования базируются на использовании математического аппарата высшей алгебры, комбинаторики, теории вероятностей, теории помехоустойчивого кодирования, имитационного моделирования, теории проектирования устройств ЭВМ.

Научная новизна работы:

1. Создан математический базис основных этапов процедур эффективной коррекции аддитивных и синхронизационных ошибок, возникающих в каналах записи/воспроизведения внешних запоминающих устройств ЭВМ, в виде совокупности лемм, теорем и утверждений, включающий:

- теорему о взаимосвязи неизвестных невязок с вытекающими из нее следствием и утверждениями, обосновывающими возможность декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния с приемлемой аппаратной сложностью;

- теорему о свойствах смежного класса с лидером веса один с вытекающими из нее следствиями, позволяющими реализовать декодирование кодов РидаСоломона с неполным вылавливанием ошибок в области проверочных символов;

- теоремы о взаимосвязи синдромов сегмента М-последовательности при его левом или правом сдвигах, позволяющие применить декодирование с вылавливанием ошибок для надежного определения фаз последовательностей сегментов.

2. Разработана система методов реализации основных этапов процедур декодирования кодов Рида-Соломона, позволяющая повысить эффективность коррекции ошибок, включающая:

- метод поиска неизвестных невязок аналитического продолжения алгоритма Берлекэмпа-Месси на две итерации, отличающийся попарным перебором позиций ошибочных символов кодового слова;

- метод определения позиций ошибочных символов в коде Рида-Соломона за границей половины минимального кодового расстояния, основанный на поиске совместимой подсистемы полиномиальных уравнений от нескольких неизвестных;

- метод пошагового исправления ошиб ок в кодовом слове, отличающийся неполным вылавливанием ошибок.

3. Разработана система методов реализации совместной коррекции аддитивных ошибок и ошибок синхронизации, позволяющая повысить эффективность коррекции ошибок и заключающаяся в:

а) введении М-последовательности в передаваемые данные, закодированные кодом Рида-Соломона;

б) оперативном восстановлении синхронизации данных при ее нарушении на основе следующих разработанных методов:

- методе коррекции вставок/выпадений символов путем двусторонней оценки локаторов групп символов данных;

- мажоритарном методе определения фаз сегментов М-последовательности;

- методе помехоустойчивого определения фаз сегментов Мпоследовательности путем интерпретации этих сегментов в качестве слов кода максимальной длины;

в) исправлении как первичных, так и вторичных аддитивных ошибок кодом Рида-Соломона.

4. На основе разработанных методов создана система алгоритмов коррекции ошибок, включающая алгоритмы:

- синдромного декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния;

- пошагового декодирования кодов Рида-Соломона, использующие неполное вылавливание ошибок в кодовом слове;

- исправления ошибок синхронизации, использующие двусторонние оценки локаторов группы символов данных.

5. Разработан математический базис синтеза основных блоков устройств коррекции ошибок, позволяющий снизить их сложность, основанный на следующих теоретически обоснованных математических процедурах и преобразованиях алгоритмов:

- параллельной организации поиска невязок при исправлении дополнительных ошибок кодом Рида-Соломона, значительно сокращающей общее число вычислений обратного элемента в конечном поле;

- использовании относительных фаз m-грамм, значительно упрощающих оценку фазы сегментов М-последовательности.

6. Разработаны варианты структурно-функциональной организации устройств коррекции ошибок, особенностью которых является введение новых функциональных блоков, реализующих:

- поиск неизвестных невязок и позиций символов ошибок в кодовом слове;

- сортировку символов кодового слова по надежности;

- вычисление коэффициентов виртуального многочлена остатка;

- двустороннюю оценку локаторов групп символов данных.

Практическая ценность.

1. Созданные алгоритмы декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния позволяют значительно повысить эффективность применения высокоскоростных кодов Рида-Соломона во внешних запоминающих устройствах ЭВМ без изменения существующих стандартов и без внесения дополнительной информационной избыточности при допустимой для современных СБИС аппаратной сложности.

2. На основе декодирования с неполным вылавливанием ошибок созданы пошаговые декодеры с минимальной задержкой декодирования и наименьшей аппаратной сложностью в своем классе.

3. Разработаны устройства коррекции ошибок синхронизации, позволяющие исправлять вставки или выпадения символов большой протяженности, сопровождающие пакеты аддитивных ошибок в канала х записи/воспроизведения со вставками/выпадениями символов.

4. Создано устройство коррекции ошиб ок для оптических накопителей информации, уменьшающее вероятность ошибок на бит в считанных данных с 10-4 до 10-11.

Реализация результатов работы.

Исследования по тематике диссертации проводились в рамка х договорных НИР КурскГТУ №1.66.00 и 1.62.00.

Результаты работы были внедрены в Институте проблем регистрации информации НАН Украины при разработке подсистемы оптической памяти и автоматизированной системы распространения компьютерной информации.

Также результаты работы были использованы в фирме Acuvision (Великобритания) при разработке аппаратуры помехоустойчивого кодирования спутниковых телекоммуникационных каналов.

Научно-методические результаты, полученные в диссертационной работе, внедрены в учебный процесс кафедры Вычислительная техника Курского государственного технического университета и использованы при проведении занятий по дисциплинам Сети ЭВМ и телекоммуникации и Технические средства защиты и сжатия информации, в дипломном проектировании, при подготовке магистерских и двух кандидатских диссертаций.

Внедрения подтверждены соответствующими актами.

Основные положения, выносимые на защиту:

1. Математический базис основных этапов процедур эффективной коррекции аддитивных и синхронизационных ошибок.

2. Система методов реализации основных этапов процедур декодирования кодов Рида-Соломона.

3. Система методов реализации совместной коррекции аддитивных ошибок и ошибок синхронизации.

4. Алгоритмы: синдромного декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния, пошагового декодирования кодов Рида-Соломона, исправления ошибок синхронизации.

5. Математический базис синтеза основных блоков устройств коррекции ошибок 6. Структурно-функциональная организация устройств коррекции ошибок.

7. Результаты исследования эффективности разработанных алгоритмов и устройств коррекции ошибок.

Апробация работы. Основные положения диссертационной работы докладывались и получили положительную оценку на следующих международных и республиканских конференциях и симпозиумах: 3-ей, 4ой, 6-ой, 8-ой Международных конференциях Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации, Курск, 1997, 1999, 2003, 2008; научнотехнической конференции Электроника и информатика-97, Москва, 1997;

9-ой, 10-ой, 11-ой, 15-ой Международных конференциях Проблемы передачи и обработки информации в сетях и системах телекоммуникаций, Рязань, 2000, 2001, 2002, 2008; Joint 1st Workshop on Mobile Future & Symposum on Trends in Communications, SympoTICТ03, Bratislava, Slovakia, 2003; IEEE International Conference on Communications, ICCТ04, Paris, France, 2004; 2nd IEEE International Conference on Circuits and Systems for Communications, ICCSC, Moscow, Russia, 2004; 1st International Symposium on Wireless Communication Systems, ISWCSТ04, Mauritius, 2004; 7-ой, 8-ой, 9-ой, 10-ой, 11-ой Международных конференциях Цифровая обработка сигналов и ее применение, Москва, 2005, 2006, 2007, 2008, 2009; 60-ой Научной сессии РНТО РЭС, посвященной дню радио, Москва, 2005; 2-ом Международном радиоэлектронном форуме Прикладная радиоэлектроника.

Состояние и перспективы развития, Харьков, 2005; 12-ой, 14-ой конференциях Современные проблемы информатизации, 2007, 2009; 9-ой Международной конференции Методы и алгоритмы прикладной математики в технике, медицине и экономике, Новочеркасск, 2009;

Международной конференции Информационно-измерительные, диагностические и управляющие системы, Курск, 2009.

Публикации. Результаты диссертационной работы отражены в печатной работе, в том числе одной монографии, 19 статьях, 10 из которых опубликованы в изданиях, входящих в перечень ВАК РФ. Оригинальность технических решений защищена 8 патентами.

В работах опубликованных в соавторстве, и приведенных в конце автореферата, лично соискателем разработаны: в [7,8,12-14,24,26,27] - алгоритм синдромного декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния, метод поиска неизвестных невязок, параллельная организация поиска невязок, структурнофункциональная организация декодера; в [33,36,38] - методика выбора вектора ошибок из списка, управление поиском неизвестных невязок с помощью оценок надежности символов кодового слова; в [41] - методика определения корректирующих возможностей кодов Рида-Соломона; в [21,22] - алгоритмы и устройства пошагового декодирования кодов Рида-Соломона;

в [5,6,10,20,23,25,51,52] Цметод коррекции вставок/выпадений символов путем двусторонней оценки локаторов групп символов данных, мажоритарный метод определения фаз сегментов М-последовательности; в [2,15,46,47,49] - алгоритмы установления синхронизации устройств коррекции ошибок; в [3,4,48,50] - структурно-функциональная организация декодеров и устройств коррекции ошибок.

Объем и структура работы. Диссертационная работа состоит из введения, пяти разделов, заключения, библиографического списка, содержащего 185 наименований, содержит 291 страницу основного текста, включая 76 рисунков и 38 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертации, сформулированы проблема, цель, задачи исследований и основные положения, выносимые на защиту, показаны научная новизна и практическая ценность, приведены результаты реализации работы.

В первом разделе рассмотрены характеристики ошибок, возникающих в каналах записи/воспроизведения ВЗУ ЭВМ, и существующие методы и аппаратные средства их коррекции.

Для рассмотрения характеристик ошибок введена структурная модель информационного канала ВЗУ ЭВМ и предложена классификация ошибок в различных сечениях канала.

Ошибки в ВЗУ ЭВМ характеризуются группированием (из-за наличия дефектов носителя), а большие пакеты аддитивных ошибок сопровождаются ошибками синхронизации.

Для характеристики исходного потока ошибок на выходе канала в диссертации использована величина PБО (вероятность ошибки на бит) и PСО (вероятность ошибки в символе). PБО для большинства ВЗУ ограничена сверху величиной 10-4 на бит.

В качестве меры достоверности информации на выходе устройств коррекции ошибок (УКО) предложено использовать среднее количество принятой пользователем безошибочной информации (в битах), приходящейся на один сбойный блок (сектор, кадр):

Nб NБП/ PСБ, где: NБП - количество информации (в битах) пользователя в блоке данных и PСБ - вероятность сбоя в блоке. Для ВЗУ ЭВМ Nб должна быть не менее 10121015 бит в зависимости от назначения информации.

Выполненный обзор известных методов защиты от ошибок показал, что основным методом для ВЗУ ЭВМ является коррекция ошибок с применением кодов Рида-Соломона (РС-кодов), которые можно описать следующим образом.

РС-коды, определенные над конечным полем CF(q=2m), характеризуются параметрами (n,k,d), где n - длина кодового слова, k - количество информационных символов в кодовом слове и d - минимальное кодовое расстояние. При этом количество проверочных символов в слове r = (n-k), и d = r+1. РС-код определяется с помощью порождающего многочлена:

b b+1 b+r -G(x) = (x - )(x - )...( x - ), где - примитивный элемент поля CF(q), b Ццелочисленная константа. Число d - tC = гарантированно исправляемых ошибок РС-кодом.

Для того, чтобы коррекция ошибок РС-кодами была принципиально возможной и обеспечивала треб уемую достоверность данных, необходимо достичь высокой помехоустойчивости групповой синхронизации.

Выполненный анализ методов групповой синхронизации в ВЗУ ЭВМ показал необходимость внесения избыточности в заголовок блока данных и использования специальных помехоустойчивых алгоритмов для обнаружения начала блока данных. Кроме этого необходимо периодически вносить избыточность в поле данных и использовать специальные помехоустойчивые алгоритмы для быстрого восстановления синхронизации при чтении данных с носителя.

Основными блоками УКО являются декодеры РС-кодов и устройства групповой синхронизации (УГС). Для оценки эффективности коррекции ошибок УКО в работе использованы две группы показателей.

Первая группа показателей характеризует способность УКО исправлять ошибки. Основным интегральным показателем в этой группе является зависимость Nб от исходных характеристик ошибок или шума в канале. Частными показателями являются зависимости BER (PБО) и BlER (PНОшБ) на выходе декодера помехоустойчивого кода (основной компоненты УКО) от исходных характеристик ошибок или шума в канале. Еще один частный показатель - число исправляемых декодером ошибок в кодовом слове.

Вторая группа показателей эффективности коррекции ошибок УКО характеризует их быстродействие и сложность аппаратной реализации.

Интегральным показателем в этой группе является следующая пара параметров, определяющая удельную пропускную способность УКО:

CLK V VCLK УКО УКО (1,2)=,, В П CLK V где (бит/такт) - пропускная способность УКО (время измеряется в УКО тактах), - число вентилей и - число бит памяти, необ ходимых для В П реализации УКО. Удельная пропускная способность зависит от используемых алгоритмов коррекции ошибок и качества синтеза УКО, определяющих вычислительную и аппаратную сложность УКО. Частными показателями являются вычислительная сложность алгоритма коррекции ошибок и задержка декодирования (коррекции ошибок).

Второй раздел посвящен синдромному декодированию кодов РидаСоломона за границей половины минимального кодового расстояния.

Число исправляемых ошибочных символов в кодовом слове ограничено для классической алгебраической процедуры синдромного d - tC = декодирования РС-кодов величиной. В конце 80-х годов прошлого века Блейхут рассмотрел возможность исправления tC+1 ошибочного символа с помощью аналитического продолжения алгоритма БерлекэмпаМесси еще на две итерации. Он предложил искать две дополнительные неизвестные невязки и позиции tC+1 ошибочных символов с помощью построения гистограмм.

В диссертации дана формализация процедуры исправления tC+ошибочных символов на основе использования подхода Блейхута и разработан новый метод поиска неизвестных невязок, имеющий меньшую вычислительную сложность, чем гистограммный метод. Формальное описание метода основывается на следующих теореме, следствии и утверждении.

C Теорема 2.1: Пусть полином локаторов ошибок (2t ) (x), C B(2t ) (x) вспомогательный полином и формальная степень полинома L2t локаторов получены после 2tC итераций алгоритма Берлекэмпа-Месси.

C L2t L2t Если < tC или > tC +1, то тогда в принятом слове не может быть tC +C C ошибок.

L2t 2tC +1 2tC +Если =tC, то тогда неизвестные невязки и, C соответствующие tC +1 ошибкам, могут быть найдены из следующей системы уравнений:

i -i C 2tC +2 = ( - Ci 2tC +1)2tC +, i=0, 1,Е, n-1, если (2t ) ( ) 0, (1) где -i -i C C Ci = B(2t ) ( ) / (2t ) ( ).(2) L2t Если = tC +1, то тогда невязки могут быть найдены из системы:

C i -i C 2tC +2 = Di - 2tC +, i=0, 1,Е, n-1, если B(2t ) ( ) 0,(3) где -i -i -2i C C Di = (2t ) ( ) /(B(2t ) ( ) ).(4) C C L2t B(2t ) (x) Следствие 2.1: Примем: P(x)= (2t ) (x), если = tC, и P(x)=, C L2t если = tC +1.

C L2t 2tC +Если = tC, то последовательности значений, полученные для C всех пар i и j уравнений системы (1), будут иметь следующий вид:

i j - , j i2t +1 = Si ={ ; j =i+1,...,n-1; P(Цj) 0}; i = 0,...,n-1- tC; P(Цi) 0. (5) C Ci - C j L2t 2tC +Если = tC +1, то последовательности значений, полученные C из системы (3), будут иметь следующий вид:

Di - D j, j i2t +1 = Si ={ ; j = i+1,...,n-1; P(Цj) 0 }; i = 0,...,n-1- tC; P(Цi) 0. (6) i j C - 2tC +Утверждение 2.1: Пусть - множество значений такое, что C полином (2t +2)(x) имеет точно tC +1 допустимых корней в поле GF(q). Пусть Wi = Cnt(Si); i = 0,..., n-1-tC; P(Цi) 0. Тогда множество состоит из всех значений l, удовлетворяющих условию wi,l = tC для всех i = 0,...,n-1-tC, P(Цi) 0 и l = 0,...,q-2.

Сущность предложенного метода поиска неизвестных невязок заключается в вычислении последовательностей Si возможных значений, j i2t +1 2tC +невязки по формулам (5) или (6) и подсчете одинаковых C значений невязок для каждой последовательности. Значения невязок, найденные в последовательности Si ровно tC раз, являются искомыми.

Алгоритм исправления tC+1 ошибочных символов, основанный на новом методе нахождения неизвестных невязок (п.4-6), приведен ниже.

1. Вычисление многочлена синдрома S(x).

2. Вычисление с использованием алгоритма Берлекэмпа-Месси многочлена C C B(2t ) (x) локаторов ошибок (2t ) (x) и вспомогательного многочлена.

C C B(2t ) (x) 3. Вычисление преобразования Фурье многочленов (2t ) (x) и.

L2t L2t 4. Вычисление коэффициентов Ci (2), если =tC, или Di (4), если =tC +1.

C C, j i2t +5. Вычисление последовательностей Si возможных значений невязки C 2tC +(5 или 6) для i =0,Е, n-1-tC, удовлетворяющих условию P(Цi) 0.

l Вычисление Wi и поиск всех , удовлетворяющих wi,l = tC для всех i = 0,...,n-1-tC, P(Цi) 0 и l = 0,...,q-2.

6. Повторное вычисление последовательности Si для найденного значения i и, j 2tC +1 i2t +фиксация позиций ошибок по условию =.

C 7. Вычисление значений ошибок и их исправление.

2tC +Показано, что число итераций поиска невязки равняется (n1+tC)(n-tC)/2. Для высокоскоростных РС-кодов (n>>tC) это число близко к n2/2. Быстродействие предложенного метода поиска невязок в 2(q-1)n/((n-1+ tC)(n-tC)) раз выше быстродействия метода поиска невязок Блейхута. Для высокоскоростных РС-кодов выигрыш по быстродействию составит 2(q-1)/n раз.

Асимптотическая сложность алгоритма растет квадратично относительно n, что значительно меньше в сравнении с алгоритмом Гурусвами ЦСудана.

Путем имитационного моделирования и аналитических расчетов был исследован выигрыш от исправления дополнительного ошибочного символа в словах различных РС-кодов, определенных над полем GF(28). В качестве модели канала использовался двоичный симметричный канал без памяти.

Результаты исследования приведены в таблицах 1 - 2.

В таблице 1 приведены доли исправляемых конфигураций ошибок веса tC+1 по отношению ко всем возможным конфигурациям ошибок этого веса для РС-кодов с различными параметрами.

Таблица 1.

Процент исправляемых конфигураций ошибок веса tC+n 30 55 80 105 130 155 180 205 230 27 67,7 0,5 0,0 0,0 0,0 0,0 0,0 0,0 0,0 0,9 99,2 82,3 24,6 0,2 0,0 0,0 0,0 0,0 0,0 0,d 11 99,9 99,3 93,5 70,4 25,5 1,7 0,0 0,0 0,0 0,13 100,0 99,9 99,7 98,1 91,4 72,7 38,5 9,2 0,0 0,15 100,0 100,0 100,0 99,9 99,5 97,8 92,6 80,1 55,9 26,17 100,0 100,0 100,0 100,0 100,0 99,9 99,5 98,1 94,8 86,Таблица 2.

Зависимость степени увеличения числа принятых бит на сбой от длины N слова РС-кода n 30 55 80 105 130 155 180 205 230 27 2,8 1,0 1,0 * * * * * * * 9 23,7 4,2 1,3 1,0 1,0 * * * * * d 11 35,1 16,1 6,9 2,7 1,3 1,0 1,0 * * * 13 42,7 21,4 13,4 8,5 5,1 2,7 1,5 1,0 1,0 1,15 51,2 23,7 15,5 11,5 9,2 6,8 4,6 2,9 1,8 1,17 59,2 26,8 18,0 13,3 10,0 8,5 7,1 5,8 4,4 3,* - моделирование не проводилось В таблице 2 показана зависимость степени увеличения числа принятых бит на сбой =Nб1/Nб0 от длины слова n РС-кода для случая исправления N одного дополнительного ошибочного символа при вероятности битовых ошибок в канале PБО =10-3. Nб1 и Nб0 - количество принятых бит на сбой в случаях исправления tC +1 и tC ошибок соответственно.

Из анализа таблицы 2 следует, что эффективности коррекции ошибок увеличивается при укорочении кода и увеличении d.

В архивных оптических накопителях типа WORM используется РС-код с параметрами (n=120, k=104, tC =8). Для этого кода количество принятых бит на сбой увеличилось в =11,3 раз. В оптических дисках DVD используется N РС-код с параметрами (n=208, k=192, tC=8). Для этого кода количество принятых бит на сбой увеличилось в =5,8 раз.

N В диссертации проведено исследование эффективности использования мягких решений при исправлении tC +1 ошибок.

Наиболее очевидный способ использовать мягкие решения для предложенного алгоритма заключается в выборе с их помощью вектора ошибок из списка, полученного на его выходе. В работе показано, что такая процедура позволяет значительно расширить область эффективного применения алгоритма декодирования относительно n. Так, для РС-кода с d=13, определенного над конечным полем GF(28), эта область увеличилась примерно в два раза. Длина слова n, при которой наблюдается увеличение основного интегрального показателя Nб эффективности коррекции ошибок в четыре раза, достигла величины 255 символов по сравнению со 1символами (см. табл. 2).

Значительно более эффективно использовать мягкие решения позволяет предложенный в диссертации метод поиска неизвестных невязок.

Для этого метода относительно просто реализовать поиск, управляемый надежностью символов. На основе мягких решений относительно отдельных бит формируются оценки надежности принятых из канала символов РС-кода.

Эти оценки используются для управления перебором по выражениям (5,6).

Модифицированные для управления надежностью формулы (5,6) показаны ниже:

L [ i ] L [ j ] - i L ЦL[j] ЦL[i] Si ={L [tC],+1[ j ] = ; j = i+1,...,n-1; P( )0 }; i= 0,...,nc; P( )0, C - C L [ i ] L [ j ] или DL[ i ] - DL[ j ] ЦL[j] ЦL[i] L[ti ], L[ j ] = Si={ 2 +1 ; j = i+1,...,n-1; P( )0 }; i =0,...,nc; P( )0, L[ i ] L[ j ] C - где L - массив номеров позиций символов принятого кодового слова, упорядоченных по возрастанию надежности символов; nc n-1-tC. При такой 2tC +организации перебора неизвестная невязка находится при малых значениях i, что обеспечивает значительное снижение сложности декодирования и увеличение быстродействия декодера. Такой поиск одновременно с повышением быстродействия позволяет решить задачу выбора наиболее вероятного вектора ошибок из списка. В подавляющем большинстве случаев невязка, соответствующая этому вектору находится первой.

Результаты исследования времени поиска неизвестных невязок, управляемого надежностью символов, в канале с аддитивным белым гауссовским шумом и модуляцией BPSK приведены на рис. 1. Путем имитационного моделирования исследовались РС-коды с d=13, определенные над конечным полем GF(28), nc = 30. На графике обозначает коэффициент уменьшения времени поиска неизвестных невязок, равный отношению произведения nSnw (где nw - число обработанных кодовых слов в процессе моделирования; nS = (n-1+tC)(n-tC)/2) к действительному числу, j i2 tC +вычислений невязок декодером при обработке nw слов. Зависимость соответствует случаю декодирования кодовых слов с tC +1 ошибкой без управления (характеризует возможность повышения быстродействия декодера за счет усреднения времени декодирования), зависимость 2 - случаю управления поиском позиций ошибок информацией о надежности принятых символов.

Рис. 1. Зависимость коэффициента уменьшения времени поиска неизвестных невязок от длины РС-кода Из графика видно, что выигрыш во времени поиска при управляемом декодировании составляет примерно два порядка.

Введение мягких решений в предложенный алгоритм декодирования РС-кодов за границей половины минимального кодового расстояния обеспечивает значительное увеличение эффективности коррекции ошибок.

На основе полученных методов и алгоритмов декодирования разработаны варианты структурно-функциональной организации декодеров РСкодов, исправляющих tC +1 ошибок. Один из вариантов приведен на рис. 2.

В работе осуществлен синтез блока поиска невязок и позиций ошибок на основе параллельной организации поиска со сниженной аппаратной сложностью. Математическим базисом, положенным в основу синтеза блока (рис. 3), является следующее утверждение.

L2t Утверждение 2.2: Если =tC, то последовательности значений C i, j i 'i,tj +1 = -1t +1 , полученные для пар i и j = i+k уравнений (1), будут 2 C C иметь вид:

k k 'i,t +1 = (Ci - Ci+k ) (1 - )-1 ; k = 1,...,n-1-i;

Si ={ C Цi-k Цi P( ) 0 }, i = 0,..., n-1-tC, P( ) 0. (7), j i 'i,tj +1 = i2t +1 L2t Если =tC +1, то последовательности значений, C C C полученные из (3), будут иметь вид:

k k 'i,t +1 = (Di - Di+k ) (1 - )-Si ={, k = 1,...,n-1-i, C Цi-k Цi P( ) 0 }, i = 0,..., n-1-tC, P( ) 0. (8) c(x) r(x) Буф е р данны х Выч и слиВыч и сли(x) S(x) П роцессор т ель те ль в полях Галуа (x) значений синдром а ош ибок (Алг орит м Control (x) Б ерлекэм паB(x) Ме с си) State {X } i {X } i i" Блок Блок поиска Ci (Di ) дискрет. невязок и Mskпреобра- по з и ц и й AddrW зования ош ибок {X } i Фурь е Рис. 2. Структурно-функциональная организация декодера РС-кода, исправляющего ошибки за границей половины минимального кодового расстояния Положенные в основу аппаратной реализации формулы (7) и (8) значительно сокращают аппаратные затраты в самом сложном блоке декодера даже при небольшой степени распараллеливания , так как делителей в поле GF(2m) заменяются на умножителей и один инвертор, вычисляющий обратное значение элемента поля. При реализации делителей и инверторов на логических элементах их сложность будет вносить основной вклад в сложность модуля. Поэтому удельная пропускная способность блока по показателю возрастет практически в раз.

В диссертации разработан алгоритм списочного декодирования РСкодов, позволяющий исправлять ошибки за границей половины минимального кодового расстояния, с величиной радиуса декодирования вплоть до n-k. Алгоритм предусматривает выполнение tE итераций (tE - число ошибок, исправляемых за границей половины минимального кодового расстояния, максимальное значение tE равно n-k- tC ), на каждой из которых осуществляется поиск позиций ошибок веса tC + v (v - номер итерации). Для этого используется метод определения позиций ошибочных символов в РСкоде за границей половины минимального кодового расстояния, основанный на поиске совместимой подсистемы полиномиальных уравнений от нескольких неизвестных.

iiState C D Control Reg k Inv 'i,tk+Ci+k(Di+k) C ( D ) i i k 1 - Reg x Count Reg k 'i+1,1 -2t+ Ci+1(Di+1) 1-k-Reg x Count Reg 1-k -'i+11,k-+Ci+-1(D+-1) i 1-k- +1 2t+ Reg x Count Рис. 3. Структурная схема блока поиска невязок и ошибок с параллельной организацией поиска невязок Разработанный в работе метод предполагает вычисление v - |s| ((s = tC Si1,i2,...,il -L2t ) наборов последовательностей возможных значений невязки C i,i2,...,il для всех возможных наборов индексов i1, i2,Е,il-1 (il = il-1+1,Е,n-1, l = 2v) и выделение значений переменной , которые встречаются точно w = tC +1-v раз в какой-то из этих последовательностей, где oF (i1, i2,..., il, Ri1, Ri2,..., Ril ) Si1,i2,...,il -1 = {i1,i2,..., il = ; il = il -1 + 1, n - 1}, o F (i1, i2,..., il, Ri1, Ri2,..., Ril ) ; (9) il -1 = il - 2 + 1, n - 1 - w,..., i = i + 1, n - w - l + j,..., i1 = 0, n - w - l + j j - o ik1 2 ik1 Fo(i1,i2,...,il, Ri1, Ri2,...,Ril ) = ( +ik ) ( +ik )Ri ;

jk { j1, j2,..., jo}=J {k1,k 2} {k1,k 2} k=1 j1< j2<...< jo k1

(2s+1)i -i -i C C B(2t ) ( ) / (2t ) ( ), если s Ri = ,i=0,Еn-1.

(-2s-1)i -i -i C C (2t ) ( ) / B(2t ) ( ), в противном случае (Если v =-s вычисляется один набор.) Если найдены значения переменной , которые встречаются точно w раз в какой-то из этих последовательностей, то значениями локаторо в ошибок являются значения индексов i1, i2,Е,il-1 этой последовательности и множество значений последнего индекса il, соответствующего таким значениям переменной .

Асимптотическая сложность разработанного алгоритма списочного декодирования растет полиномиально относительно n для фиксированного tE.

Для малых значений tE сложность растет значительно медленнее в сравнении с алгоритмом Гурусвами ЦСудана (GS-алгоритмом).

Гистограмма рис. 4 характеризует корректирующую способность РСкодов с d=17, определенных над полем GF(28), при их декодировании алгоритмами, не использующими мягкие решения. Радиус декодирования tmax соответствует случаю, когда на выходе списочного декодера преобладают (не менее 80%) списки с не более чем одной конфигурацией ошибок (ряд 1).

Также на гистограмме приведено число ошибок tGS, которые можно исправить с помощью GS-алгоритма (ряд 2) и число гарантированно исправляемых РС-кодом ошибок tC (ряд 3).

Рис. 4. Исправляющая способность различных алгоритмов декодирования РС-кодов над GF(28) с d=Разработанный алгоритм списочного декодирования позволяет исправлять tmax ошибок. Из гистограммы следует, что алгоритм ГурусвамиСудана не эффективен для высокоскоростных кодов при n = 105,Е,255, где tGS = tC, да и для кодов с меньшими скоростями не использует всех их потенциальных корректирующих возможностей, так как tGS < tmax.

В третьем разделе рассмотрено декодирование кодов Рида-Соломона на основе разработанного метода пошагового исправления ошибок с неполным их вылавливанием, позволяющем реализовать потоковые декодеры РС-кодов с минимальной задержкой декодирования.

Метод пошагового исправления ошибок для РС-кодов, предусматривающий неполное (частичное) их вылавливание в области проверочных символов, основан на следующих теореме и следствиях, доказанных в диссертации.

Теорема 3.1: Пусть два произвольно выбранных коэффициента qi и qj полинома остатка q(x)=ResG(x)r(x) (r(x)Цпринятое из канала слово), все коэффициенты которого ненулевые, имеют свойства:

i j qi/gi qj/gj, qi/(gi ) qj/(gj ).

Смежный класс РС-кода имеет лидер веса один с ненулевой компонентой, расположенной в информационной части слова, тогда и только тогда, когда другие d-3 коэффициента полинома остатка q(x) связаны с выбранными коэффициентами следующим образом:

l i j i l j j i l ql=gl ( + )/[qi-1gi ( + )+qj-1gj ( + )], l=0,.,d-2; l i,j b+d-2 d-G(x) j j где g(x) = (x - ) = = g x.

j b (x - ) j=b+1 j=Следствие 3.1: Пусть в информационной части кодового слова РСкода произошла одна ошибка. Тогда справедливо следующее:

i l j j i l l i j qi-1gi ( + ) +qj-1gj ( + ) +ql-1gl ( + ) = 0. (10) где qi, qj, ql - произвольно выбранные коэффициенты полинома остатка q(x).

Уравнение (10) не может выполняться при наличии двух ошибок в информационной части кодового слова.

Следствие 3.2. Если в первых n-1 символах кодового слова РС-кода произошло t ошибок (1

qi 0, qj 0, i j qi/gi qj/gj, qi/(gia ) qj/(gja ), (11) l i j i l j j i l ql=gla (a +a )/[qi-1gia (a +a )+qj-1gja (a +a )], l=1,.,d-2, li,j, где i и j любые ненулевые не равные друг другу целые числа меньшие d-1.

Предлагаемый метод пошагового исправления ошибок подразумевает исправление ошибки в одном фиксированном проверочном символе ri слова РС-кода. Значение ошибки для этого проверочного символа представляет собой функцию от q(x): Y=f(q(x)). После выполнения циклического сдвига определяют значение ошибки для следующего символа кодового слова.

Процедура повторяется до тех пор, пока не будут обработаны все символы.

Декодирование с неполным вылавливанием ошибок возможно при обнаружении фиксированного числа ошибок, оставшихся в области информационных символов, и учете их влияния на компонент синдрома qi.

Это обеспечивается использованием Теоремы 3.1. и ее следствий.

Алгоритм процедуры пошагового декодирования с неполным вылавливанием ошибок для РС-кода с d=5 приведен ниже:

m q(x) := Re sG (x)[r(x) x(2 -n+i) ].

1. Вычисление многочлена синдрома 2. j := n-1.

0, если wt(q(x)) = q0, если 0 < wt(q(x)) Y = f (q(x)) = 3., 0, если wt(q(x)) > 2 и (10) не выполняетс я q0-qm0, если wt(q(x)) > 2 и (10) выполняетс я где qm0=g0a0(ai+aj)/[qi-1giai(a0+aj)+ qj-1gjaj(ai+a0)], i, j, l в (10) принимают значения 3, 2, 1 в любом порядке 4. rj := rj - Y.

q(x) := Re sG( x)[q(x) x ] 5..

6. j := j-1.

7. Если j 0, переход к п. 3, в противном случае Конец.

Структурно-функциональная организация пошагового потокового декодера, реализующего исправление ошибок в соответствии с разработанным алгоритмом, приведена на рис. 5. Декодер позволяет исправлять ошибки в данных в темпе их вывода в выходной порт сразу же после завершения приема данных в б уферное ОЗУ.

r(x) c(x) Задержка на n символов + Y(x) qя и и В и + н Б ц а а в q к о а а и р м м н и ф о и мо р а q2 qm1 в р др е ур. (10) д д р о о и н н С мн и ф и е с с а л а q3 qmс м м и е е В х ч х Б С ы С В wt = Вес q(x) wt Рис. 5. Структурно-функциональная организация декодера РС-кодов, реализующего декодирование с неполным вылавливанием ошибок: БВ - блок вентилей Самый сложный блок пошагового декодера - блок вычисления значений qm0 и qm1 содержит только 2 сумматора, 5 умножителей на постоянные коэффициенты и 4 инвертора в конечном поле Галуа. Удельная пропускная способность разработанного декодера возросла в сравнении с лучшим из известных пошаговых декодеров с такой же корректирующей способностью по параметру 1 в =2,3 раза, по 2 в =1,3 раза (m=8).

1 Для уменьшения вероятности ошибочного декодирования (актуально для некоторых приложений, использующих РС-коды с небольшим d).

разработан пошаговый декодер с блокировкой ложной коррекции. Алгоритм декодирования отличается видом функции Y=f(q(x)), предотвращающей ложную коррекцию для РС-кодов с d >5:

0, если wt(q(x)) = q0, если 0 < wt(q(x)) Y = f (q(x)) = 0, если wt(q(x)) > 2 и (11) не выполняется (12) 0 i j i 0 j j i q0- g0 ( + )/[qi-1gi ( + ) + q-1g ( + )], j j если wt(q(x)) > 2 и (11) выполняется.

В формуле (12) i и j могут выбираться произвольно, l в системе уравнений (11) не должно равняться 0.

Функциональная схема пошагового декодера с блокировкой ложной коррекции приведена на рис. 6.

Рис. 6. Функциональная схема пошагового декодера с блокировкой ложной коррекции Декодер обеспечивает гарантированное исправление до двух ошибочных символов в кодовом слове РС-кода и блокировку ложной коррекции при наличии в слове от трех до tD+2 (tD = r-4) ошибочных символов.

Сложность комбинационно-логической схемы вычисления Y разработанного декодера определяется следующим образом: в=(25r23)m+2r+83 и =r2mm. При реализации вычислений над полем GF(28) п декодер может корректировать ошибки в потоке данных, передаваемых со скоростью 1 Гбит/с, при работе на тактовой частоте 250 МГц. Параметры удельной пропускной способности декодера: 1 =3,610-3, 2 =3,310-4 (r=6).

В диссертации разработан алгоритм пошагового декодирования выколотых РС-кодов, основанный на предложенном методе пошагового исправления ошибок с неполным их вылавливанием. При этом вычисление значения ошибки Y на каждом шаге осуществляется с учетом наличия на первых шагах в многочлене остатка q(x) компонент, искаженных выколотыми символами. На первых шагах наряду с исправлением ошибок осуществляется восстановление выколотых символов по следующей формуле:

0, еслиwt(q(x)) qp ''= p j p j j p gp (i + )/[qi-1gii ( + ) + q-1g ( +i )],еслиwt(q(x)) >1, j j где p - количество выколотых символов.

На основе разработанных алгоритмов синтезированы пошаговые декодеры выколотых РС-кодов.

Четвертый раздел посвящен коррекции ошибок в каналах со вставками/выпадениями символов.

В таких каналах, присущим большинству ВЗУ ЭВМ, эффективность исправления ошибок РС-кодами будет невысока без оперативного восстановления синхронизации символов в блоке данных.

В диссертации разработана система методов совместной коррекции аддитивных ошибок и ошибок синхронизации, предусматривающая восстановление синхронизации с использованием М-последовательности с последующим исправлением как первичных, так и вторичных аддитивных ошибок РС-кодом.

М-последовательность представляет собой двоичную линейную рекуррентную последовательность, каждый член которой с номером j+m является линейной комбинацией предшествующих m членов (m - порядок последовательности):

sj+m=am-1 sj+m-1 +am-2 sj+m-2 + Е +a0 sj, где коэффициенты ai принимают значения из двоичного поля. Период такой последовательности равен n = 2m-1. Сегмент М-последовательности, состоящий из l следующих подряд символов, называется l-граммой.

Важными частными случаями l-граммы являются n-грамма (l=n) и m-грамма (l=m). По любой m-грамме можно восстановить всю М-последовательность.

В работе под фазой данной l-граммы понимается ее расположение в М-последовательности с неоднозначностью kn (k - целое):

= i mod n, где i - индекс первого элемента l-граммы (si) в М-последовательности.

l m Любые фиксированные m бит l-граммы ( ) однозначно определяют ее фазу. Значение фазы удобно вычислять как табличную функцию от последовательности символов m-граммы, расположенной в определенном месте l-граммы.

Быстрое восстановлении синхронизации основывается на разработанных в диссертации методе коррекции вставок/выпадений символов путем двусторонней оценки локаторов групп символов данных и помехоустойчивых методах определения фаз l-грамм М-последовательности.

Метод коррекции вставок/выпадений символов заключается в следующем.

Вставленная в данные М-последовательность разбивает поток символов на группы из символов. Назовем последовательность из lсимволов, выбранную из потока данных в канале с периодом , l-группой (rt, rt+p, rt+2p, Е, rt+(l-1)). Определим следующим образом фазу l-группы:

= t mod , где t - индекс первого элемента l-группы.

Фаза l-группы характеризует ее расположение относительно символов М-последовательности, она определяет смещение первого символа l-группы относительно ближайшего слева символа М-последовательности. В случае =0, l-группа является l-граммой. Если l=1, то l-группа вырождается в один канальный символ rt, и фаза характеризует его расположение относительно М-последовательности.

На приемном конце М-последовательность используется для оценки расположения групп данных в потоке. Для этого из принятого потока символов выделяются подпоследовательностей, каждая из которых состоит из выбранных с периодом символов потока.

В подпоследовательностях выделяются левые и правые окрестности оцениваемой группы данных, имеющие один общий символ (левая окрестность содержит символы, раньше поступившие из канала). Каждая окрестность состоит из l символов и представляет собой l-группу. l-группа может содержать до h (h = l-m+1) последовательных m-грамм Sj = (sj, sj+1,Е,sj+m-1) (для левой окрестности j=i-h-m+2,Е,i-m+1, для правой j=i,Е,i+h-1).

Затем среди левых и правых окрестностей выделяется по одной окрестности, с наибольшей достоверностью содержащей l-грамму Мпоследовательности.

На основании фазы наиболее достоверной из этих двух l-грамм и фазы соответствующей l-группы формируется оценка расположения группы данных в потоке (локатор), после чего вычисляется адрес размещения этой группы в б уферном оперативном запоминающем устройстве (ОЗУ) и осуществляется ее запись. Таким же об разом осуществляется запись в ОЗУ следующих групп данных. Последовательно считанные данные из б уферного ОЗУ б удут содержать только аддитивные ошибки без ошибок синхронизации.

Формальное описание процедуры исправления ошибок синхронизации приведено ниже в виде алгоритма:

1. t:=0.

2. Rr:= shift(Rr,rt); Rl := shift(Rl,rt-).

3. Если t >=, переход к шагу 4, в противном случае переход к шагу 9.

rr 4. Нахождение оценок фазы, фазы l-граммы с достоверностью для r r t- l Rr. Нахождение оценок фазы, фазы l-граммы с достоверностью l l rt - для Rl.

r l 5. Если >, то := и L*:= ; в противном случае := и L*:= .

r l r l rt- rt- rt- rt- 6. Если =0, переход к шагу 7, в противном случае переход к шагу 9.

7. Если блокировка по вставке, переход к шагу 9, в противном случае переход к шагу 8.

8. RAM(L*) :=(rt-, rt+1-,Е, rt+-1-).

9. t :=t +1.

10. Если все данные обработаны, завершение алгоритма, в противном случае переход к шагу 2.

В описании алгоритма используются следующие обозначения:

t - номер последнего символа, поступившего на вход устройства коррекции ошибок синхронизации;

- задержка оценки расположения группы данных в потоке, измеренная в символах, =(l-1);

Rr Цстрока, содержащая символы правых окрестностей символа rt-;

Rl - строка, содержащая символы левых окрестностей символа rt-;

shift(R,r) - сдвиг элементов строки R, при этом правый элемент строки из нее удаляется, элемент r помещается на место левого элемента;

и - оценки фаз наиболее достоверных l- грамм правых и левых r l окрестностей символа rt-;

и - меры достоверности определения l- грамм правых и левых r l окрестностей;

r l - rt- rt - и rt- оценки справа и слева фазы символа относительно Мпоследовательности;

- rt-;

rt - итоговая оценка фазы символа L* - оценка локатора группы данных с первым символом rt- (значения L* и rt - определяют расположение группы данных в потоке);

RAM - массив, в который записываются группы данных (rt-, rt+1-,Е, rt+-1-) (представляет в алгоритме буферное ОЗУ).

Разработанный метод позволяет с высокой точностью (до периода вставки М-последовательности ) восстанавливать синхронизацию, нарушенную из-за вставок или выпадений символов большой протяженности, сопровождающих пакеты аддитивных ошибок.

Структурно-функциональная организация устройства коррекции ошибок синхронизации, построенного в соответствие с вышеописанным методом приведена на рис. 7.

Входные 1 символы rt- Регистр сдвига FIFO rt ) 1 p + t r, Блок оценки пр авы х Блок оценк и левы х Е, окрестностей окрестностей + t r, r - l t r rt - r r l rt - l ( > Выходные DI DO данные Mux 6 RAM AI AO L* Адрес Mux чтения W R выходных rt - данных Строб == чтения С0Т Рис. 7. Структурно-функциональная организация устройства коррекции ошибок синхронизации Фаза l-граммы может быть определена по значению любой входящей в нее в известном месте m-граммы:

= (m - j) mod n, (13) m где - фаза m-граммы, j - смещение m-граммы относительно начала lграммы (j=0,Е,l-m). Однако для повышения помехоустойчивости необходимо определять фазу, используя все символы l-граммы.

В диссертации разработан итеративный мажоритарный метод определения последовательности фаз l-грамм, в котором оценка фазы lграммы формируется путем мажоритарной обработки значений фаз, даваемых всеми m-граммами l-граммы. В качестве фазы l-граммы выбирается фаза, набравшая максимальное число УголосовФ m-грамм. Это число УголосовФ может служить естественной оценкой достоверности определения фазы.

Вычислительная сложность пересчета значений фаз m-грамм к началу l-граммы (13) может быть значительно уменьшена путем использования относительных фаз m-грамм, определяемых следующим образом.

Фаза m-граммы (rt-(m-1), rt-(m-2),Е, rt-, rt) из последовательности входных символов {rt} может быть представлена в следующем виде:

L(rt-(m-1) p,rt-(m-2) p,...,rt- p,rt ) = (B(t) + Rt ) modn t = (m-1)p,...,,, где L( ) - табличная функция, дающая фазу m-граммы в зависимости от ее содержания; B(t) - целочисленная функция, значение которой инкрементируется по модулю n после обработки каждых символо в B(t) = ( t / p + K) modn, K - целочисленная константа; Rt - относительная фаза m-граммы. Тогда Rt = (L(rt-(m-1) p,rt-(m-2) p,...,rt- p,rt) - B(t))modn, t =(m-1)p,...,.

Последовательность относительных фаз m-грамм, вычисленная для подпоследовательности данных, содержащей М-последовательность, будет состоять из одинаковых элементов в случае отсутствия ошибок.

Последовательности относительных фаз m-грамм, вычисленные для других подпоследовательностей, б удут состоять из произвольного набора чисел, зависящих от передаваемых данных.

На основе мажоритарного метода определения последовательности фаз l-грамм разработаны алгоритм и устройство коррекции ошибок синхронизации (УКОС).

Эффективность алгоритма применительно к сектору данных, содержащему 10 перемеженных слов РС-кода (120,104), исследована путем имитационного моделирования. В качестве источника ошибок использовалась модель Беннета-Фройлиха, модифицированная с целью ввода ошибок синхронизации. В таблице 3 приведена зависимость степени увеличения числа принятых бит на сб ой от параметра группирования g N при вероятности битовых ошибок в канале PБО=310-3 и =25. В качестве базы для сравнения использовалась кодовая конструкция, используемая в оптических дисках типа WORM, с байтовыми ресинхронизаторами, вставленными через каждые 20 байт данных. Lгр - максимальная длина пакета аддитивных ошибок, при которой еще отсутствуют сбои синхронизации.

Таблица 3.

Зависимость степени увеличения числа принятых бит на сбой от N параметра группирования g g 0,2 0,4 0,6 0,Lгр=3 6,3 72,4 540,4 55Lгр=12 1,8 2,1 7,0 10Устройство обрабатывает один входящий символ за 10 тактов, что позволяет при реализации его на современных ПЛИС с тактовой частотой 200-500 МГц обеспечить пропускную способность 20-50 Мбит/с при параметрах удельной пропускной способности: =2.210-5, =1.810-6.

1 Значительно более быстродействующее УКОС с несколько худшим показателем эффективности коррекции Nб может быть реализовано на основе разработанного в диссертации метода помехоустойчивого определения фаз последовательностей сегментов М-последовательности (n-грамм), основанного на интерпретации n-грамм в качестве слов кода максимальной длины.

Итеративная процедура определения фаз для первой последовательности n-грамм основывается на следующей теореме.

Теорема 4.1: Пусть vi(x) и vi+1(x) обозначают слова циклического кода, соответствующие двум соседним (сдвинутые на один символ) n-граммам, принятым из канала:

vi(x) =vi xn-1 +vi+1 xn-2 + Е +vi+n-2 x +vi+n-1, vi+1(x) =vi+1 xn-1 +vi+2 xn-2 + Е +vi+n-1 x +vi+n, vi =si +ei, где si - символ m-последовательности и ei - соответствующий ему символ ошибки. Пусть qi(x) - синдром кодового слова vi(x):

qi(x) =Resg(x)(vi(x)), где g(x) - порождающий многочлен М-кода.

Тогда синдром qi+1(x) кодового слова vi+1(x) может быть получен из синдрома qi(x) кодового слова vi(x) следующим образом:

qi+1(x) =Resg(x) (qi(x)x) + (vi+n Цvi).

Процедуру определения фаз для первой последовательности n-грамм можно описать следующим образом. При вычислении фазы следующей nграммы осуществляется одна итерация деления многочлена qi(x), умноженного на x, на порождающий многочлен g(x). При этом одновременно прибавляется к свободному члену многочлена остатка сумма по модулю входящего в n-грамму символа vi+n и выходящего из нее символа vi. Если вес получившегося многочлена остатка qi+1(x) меньше порога t, это значит, что многочлен qi+1(x) содержит конфигурацию ошибок, которая может быть исправлена. В этом случае к символам опорной m-граммы, соответствующим последним символам n-граммы, прибавляются значения m младших коэффициентов многочлена qi+1(x). Исправленная опорная m-грамма используется в качестве аргумента табличной функции для получения значения фазы. Вес многочлена qi+1(x) дает оценку надежности определения фазы.

Для надежного определения фазы n-граммы второй последовательности необ ходимо вычислить синдром соответствующего слова М-кода, интерпретируя символы при m младших степенях многочлена кодового слова как информационные. Такой синдром qm(x) б удем называть m-модифицированным, поскольку он может быть получен очевидным образом путем m-кратной модификации многочлена q(x) по формуле Меггита. Последовательность m-модифицированных синдромов может вычисляться итеративно на основе доказанной в диссертации следующей теоремы.

Теорема 4.2: Пусть Rev(p(x)) обозначает многочлен возвратный к многочлену p(x). Тогда m-модифицированным синдром qmi+1(x) кодового слова vi+1(x) может быть получен из m-модифицированного синдрома qmi(x) кодового слова vi(x) следующим образом:

qmi+1(x) =Resg(x) (qmi(x)x) + (vi+n Цvi) Rev(Res ( xn-1)). (14) Rev(g(x)) Процедура определения фаз для второй последовательности n-грамм выполняется аналогично процедуре для первой последовательности с небольшими отличиями. Во-первых, при итеративном вычислении синдромов используется константный корректирующий многочлен Rev(Res (xn-1)) (14), который прибавляется к многочлену qmi(x)x, если vi+n vi.

Rev(g(x)) Во-вторых, к символам опорной m-граммы прибавляются значения m старших, а не младших коэффициентов многочлена qmi+1(x), поскольку в этом случае опорная m-грамма находится в начале n-граммы.

На основе итеративного метода помехоустойчивого определения фаз последовательностей n-грамм разработаны алгоритм и устройство коррекции ошибок синхронизации. Разработанное УКОС обрабатывает один символ Мпоследовательности за один такт, и его пропускная способность значительно выше, чем у УКОС, в котором используется мажоритарный метод (примерно на порядок), при параметрах удельной пропускной способности равных: = 8,210-5, =1,610-4.

Пятый раздел посвящен разработке и экспериментальной проверке устройств коррекции ошибок (УКО) информационных каналов ВЗУ ЭВМ.

Обоснованы принципы структурно-функциональной организации УКО ВЗУ ЭВМ, основанные на учете статистических характеристик ошибок в канале и конвейерной организации вычислений.

Осуществлен синтез ряда основных блоков УКО: устройств кодирования и вычисления синдромов и устройств групповой синхронизации.

Таблица 4.

Достигнутые показатели эффективности коррекции ошибок Алгоритмы Аппаратные средства Алгоритм Алгоритм Алгоритм Блок по- Пошаго- УКОС УКОС декодиро- списочно- исправле- иска не- вый де- (мажор. (опред.

вания РС- го деко- ния оши- вязок и кодер метод фаз с кодов с дирова- бок син- позиций РС- опред. испольисправле- ния РС- хрониза- ошибок кодов фаз) зованинием tC+1 кодов ции РС-де- ем Мошибок кодера кодов) 1= 1 = 1 = число N=313 3,810-5, 2,210-5, 8,210-5, исправл.

N=27 1=2,3, 2= 2 = 2 = ошибок 1,410-5 2=1,3 1,810-6 1,610-1(n-k) Сложность 1=100, O(n2) 2=1мяг.реш.

Созданы УКО подсистемы оптической памяти ОМЗУ-3 и УКО адаптера вещательной системы распространения компьютерной информации АСРКИ. Для них разработаны форматы хранения и передачи информации, структурные схемы. Исследована эффективность этих УКО.

В заключении приведены основные результаты работы.

Показатели эффективности коррекции ошибок, достигнутые в ходе решения проблемы приведены в таблице 4.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ В диссертационной работе в рамках решения поставленной научнотехнической проблемы повышения эффективности коррекции ошибок, возникающих в каналах записи/воспроизведения внешних запоминающих устройств ЭВМ, получены следующие основные результаты:

2. Разработана система методов реализации основных этапов процедур декодирования кодов Рида-Соломона, позволяющая повысить эффективность коррекции ошибок, включающая методы:

- поиска неизвестных невязок аналитического продолжения алгоритма Берлекэмпа-Месси на две итерации, вычислительная сложность которого меньше сложности гистограммного метода Блейхута более чем в два раза;

- определения позиций ошибочных символов в коде Рида-Соломона за границей половины минимального кодового расстояния, основанный на поиске совместимой подсистемы полиномиальных уравнений от нескольких неизвестных;

- пошагового исправления ошибок в кодовом слове, отличающийся неполным вылавливанием ошибок.

3. Введено управление поиском неизвестных невязок надежностью символов принятого из канала слова кода Рида-Соломона. Проведенные путем имитационного моделирования на ЭВМ исследования показали, что удельная пропускная способность декодера при использовании этого метода увеличивается примерно на два порядка.

4. Разработан алгоритм синдромного декодирования кодов РидаСоломона, исправляющий tC+1 ошибок. Асимптотическая вычислительная сложность алгоритма описывается квадратичной зависимостью от длины кодового слова, что значительно меньше сложности алгоритма ГурусвамиСудана. Показано, что его применение к высокоскоростным РС-кодам, используемым в ВЗУ ЭВМ дает значительное увеличение эффективности коррекции ошибок по сравнению с классическими алгоритмами декодирования.

5. Разработан алгоритм списочного декодирования кода РидаСоломона, позволяющий увеличить радиус декодирования вплоть до n-k.

Показано, что этот алгоритм позволяет значительно лучше использовать корректирующие возможности высокоскоростных кодов, используемых в ВЗУ ЭВМ 6. Разработаны алгоритм пошагового декодирования РС-кодов с блокировкой ложной коррекции, обеспечивающий при простой аппаратной реализации и минимальной задержки декодирования низкую вероятность ложной коррекции, и алгоритм пошагового декодирования выколотых РСкодов, обеспечивающий простую аппаратную реализацию и минимальную задержку декодирования.

7. Разработаны варианты структурно-функциональной организации декодеров РС-кодов, исправляющих ошибки за границей половины минимального кодового расстояния. Полученные математические соотношения для вычисления последовательностей невязок положены в основу синтеза блока поиска невязок и позиций ошибок с параллельной организацией вычислений, позволяющего значительно увеличить удельную пропускную способность декодера.

8. Разработаны варианты структурно-функциональной организации пошаговых декодеров РС-кодов, использующих неполное вылавливание ошибок и обеспечивающие высокую удельную пропускную способность.

Разработаны: пошаговый декодер с блокировкой ложной коррекции;

пошаговый декодер для выколотых РС-кодов с восстановлением выколотых символов.

9. Разработана система методов реализации совместной коррекции аддитивных ошибок и ошибок синхронизации, позволяющая повысить эффективность коррекции ошибок и заключающаяся в:

а) введении М-последовательности в передаваемые данные, закодированные кодом Рида-Соломона;

б) быстром восстановлении синхронизации данных при ее нарушении на основе следующих разработанных методов:

- методе коррекции вставок/выпадений символов путем двусторонней оценки локаторов групп символов данных;

- мажоритарном методе определения фаз сегментов М-последовательности;

- методе помехоустойчивого определения фаз сегментов Мпоследовательности путем интерпретации этих сегментов в качестве слов кода максимальной длины с использованием декодирования с вылавливанием ошибок;

в) исправлении как первичных, так и вторичных аддитивных ошибок кодом Рида-Соломона.

Использование относительных фаз m-грамм в мажоритарном методе определения фаз сегментов М-последовательности значительно упрощает оценку фазы сегмента. Это в свою очередь позволяет увеличить удельную пропускную способность устройства коррекции ошибок синхронизации. Еще большую удельную пропускную способность обеспечивает метод помехоустойчивого определения фаз сегментов М-последовательности путем интерпретации этих сегментов в качестве слов кода максимальной длины.

10. Разработаны варианты структурно-функциональной организации устройств коррекции ошибок синхронизации, использующих новые методы помехоустойчивого определения фаз сегментов М-последовательности.

11. Созданы опытные образцы устройства коррекции ошибок подсистемы оптической памяти ОМЗУ-3, экспериментальное исследование которых подтвердило достижение необходимой степени достоверности считываемых с носителя данных. Создано устройство коррекции ошибок адаптера вещательной системы распространения компьютерной информации АСРКИ, внедренное в серийное производство.

СПИСОК ОСНОВНЫХ ПУБЛИКАЦИЙ Монография 1. Егоров, С.И. Коррекция ошибок в информационных каналах периферийных устройств ЭВМ [Текст]: монография / С.И. Егоров; Курск.

гос. техн. ун-т. Курск, 2008. 252 с.

Статьи в журналах, входящих в перечень ВАК РФ 2. О повышении надежности синхронизации в НМЛ при использовании кодов Рида-Соломона [Текст] / В.А.Новиков, А.П.Типикин, П.Е.Добрянский, С.И.Егоров // Вопросы радиоэлектроники. Серия ЭВТ: Вып.5. М.: НИИЭИР, 1984. С. 39-46.

3. Новиков, В.А. Устройство исправления ошибок в НМЛ кодом РидаСоломона [Текст] / В.А.Новиков, А.П.Типикин, С.И.Егоров, // Вопросы радиоэлектроники. Серия ЭВТ: Вып.5. М.: НИИЭИР.1986. С.79-90.

4. Егоров, С.И. Вещание цифровых данных по аналоговым телевизионным каналам: от телетекста до IP-пакетов [Текст] / С.И.Егоров, А.П.Типикин // Телекоммуникации. 2000. N1. C. 26-40.

5. Глухарев, И.Н. Измерение характеристик ошибок в цифровых каналах передачи информации [Текст] / И.Н.Глухарев, С.И.Егоров, А.П.Типикин // Телекоммуникации. 2002. N8. C. 16-23.

6. Глухарев, И.Н. Корреляционный и локаторный методы измерения параметров ошибок синхронизации в цифровых каналах передачи информации информации [Текст] / И.Н.Глухарев, С.И.Егоров, А.П.Типикин // Телекоммуникации. 2003. №12. C. 12-18.

7. Egorov, S. A Modified Blahut Algorithm for Decoding Reed-Solomon Codes Beyond Half the Minimum Distance [Text] / S.Egorov, G.Markarian, K.Pickavance // IEEE Trans. on Commun. Vol. 52, № 12. 2004, P. 2052-2056.

8. Егоров, С.И. Повышение эффективности исправления ошибок помехоустойчивыми кодами Рида-Соломона в цифровых телекоммуникационных каналах [Текст] / С.И.Егоров, Г.Маркарян // Телекоммуникации. 2005. №10. С.2-8.

9. Егоров, С.И. Расширение возможностей техники вылавливания ошибок для декодирования кодов Рида-Соломона [Текст] / С.И.Егоров // Телекоммуникации. 2006. №12. C. 21-26.

10. Егоров, С.И. Метод исправления ошибок в информационных каналах путем мажоритарной обработки М-последовательности [Текст] / С.И.Егоров, А.М.Проценко, В.С.Титов // Известия ВУЗов. Сер.

Приборостроение. 2007. Т.50, №3. С.29-34.

11. Егоров, С.И. Помехоустойчивое определение фаз n-грамм Mпоследовательности [Текст] / С.И.Егоров // Известия ВУЗов. Сер.

Приборостроение. 2007. Т.50, №5. С.35.-40.

Статьи в трудах зарубежных конференций 12. Egorov, S. A Modified Blahut Algorithm for Decoding Reed-Solomon Codes Beyond Half the Minimum Distance [Text] / S.Egorov, G.Markarian // Proc. SympoTICТ03: Joint 1-st Workshop on Mobile Future & Symposium on Trends in Communications, October 26-28. Bratislava, 2003. P. 17-20.

13. Egorov, S. An Algorithm for t+1 Error Correction in Reed-Solomon Codes [Text] / S.Egorov, G.Markarian // Proceedings ICCТ04: 2004 IEEE International Conference on Communications, June 20-24. Paris, 2004. Vol.2, P.

651-655.

14. Egorov, S. An Enhanced Reed-Solomon Decoder for Wireless Communication Systems [Text] / S.Egorov, G.Markarian // Proceedings of ISWCSТ04: 1st International Symposium on Wireless Communication Systems, September 20-22. Mauritius, 2004, P. 198-202.

Прочие статьи, материалы конференций 15. Типикин, А.П. Цифровой демодулятор для оптического диска [Текст] / А.П.Типикин, С.И.Егоров, А.Г.Пеньков // Оптическая запись информации: сб. науч. тр. / редкол.: Е.В.Петров (отв. ред.) [и др.] Киев:

Наукова думка, 1987. С. 21-28.

16. Егоров, С.И. О программно-аппаратной реализации декодеров кода Рида-Соломона для защиты от ошибок малогабаритных оптических накопителей [Текст] / С.И.Егоров // Курск. политехн. ин-т. Курск, 1990. 39с.

Деп. в ИНФОРМПРИБОР, №4898.

17. Егоров С.И. Алгоритмы пошагового декодирования РСБКР-кодов [Текст] / С.И.Егоров // Методы и средства систем обработки информации: сб.

науч. ст. / Курск. гос. техн. ун-т. Курск, 1997. С.71-80.

18. Егоров, С.И. Защита от ошибок службы вещания данных по телевизионному каналу [Текст] / С.И.Егоров // Электроника и информатика97: тез. докл. 2-ой всероссийской науч.-техн. конф. М.: МИЭТ, 1997. С. 34-35.

19. Егоров, С.И. Иерархическая реализация защиты от ошибок службы вещания данных по телевизионному каналу [Текст] / С.И.Егоров // Оптикоэлектронные приборы и устройства в системах распознавания образов, обраб.

изображ. и символьной информ.: матер. 3-ей Междунар. науч.-техн конф.

Курск: Курский гос. техн. ун-т, 1997. С. 118 -120.

20. Егоров, С.И. Исправления ошибок типа вставок/выпадений бит в каналах передачи цифровой информации [Текст] / С.И.Егоров, А.М.

Проценко // Оптико-электронные приборы и устройства в системах распознавания образов, обраб. изображ. и символьной информ.: матер. 4-ой Междунар. науч.-техн конф. Курск: Курский гос. техн. ун-т, 1999. С. 147-149.

21. Егоров, С.И. Пошаговый декодер выколотых кодов Рида-Соломона для гибридных FEC + ARQ систем защиты от ошибок, использующий исключение выколотых символов [Текст] / С.И.Егоров, В.Е.Сошников // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: матер. 9-й Междунар. науч.-техн. конф. Рязань: Ряз. обл.

ин-т развития образования, 2000. С. 109-111.

22. Егоров, С.И. Пошаговое декодирование выколотых кодов РидаСоломона методом восстановления выколотых символов [Текст] / С.И.Егоров, В.Е.Сошников // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: матер. 9-й Междунар. науч.-техн. конф.

Рязань: Ряз. обл. ин-т развития образования, 2000. С. 111-114.

23. Егоров, С.И. Защита от ошибок синхронизации в системах передачи и хранения информации [Текст] / С.И.Егоров, А.М.Проценко // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций:

матер. 10-ой Междунар. науч.-техн. конф. Рязань: Рязанская гос. радиотехн.

академия, 2001. С. 89-91.

24. Егоров, С.И. Алгоритм исправления ошибок за границей половины минимального расстояния помехоустойчивых кодов Рида-Соломона [Текст] / С.И.Егоров, Г.Маркарян, К.Пикеванс // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: матер. 11-ой Междунар.

науч.-техн. конф. Рязань: Рязанская гос. радиотехн. академия, 2002. С. 73-75.

25. Егоров, С.И. Исправление ошибок синхронизации в каналах передачи данных путем декодирования M-кодов [Текст] / С.И.Егоров, А.М.Проценко // Оптико-электронные приборы и устройства в система х распознавания образов, обраб. изображ. и символьной информ.: матер. 6-ой Междунар. науч.-техн. конф. Курск: Курский гос. техн. ун-т, 2003. С. 168170.

26. Egorov, S. Error Correction Beyond the Conventional Error Bound for Reed-Solomon Codes [Text] / S.Egorov, G.Markarian // Journal of Electrical Engineering. 2003. №11-12. P.305-310.

27. Egorov, S. A Reed-Solomon Decoder Correcting Errors Beyond Half the Minimum Distance [Text] / S.Egorov, G.Markarian // Proceedings of ICCSC 2004, 2nd IEEE International Conference on Circuits and Systems for Communications, June 30 - July 2, Moscow, 2004. P.48.1-48.4.

28. Егоров, С.И. Декодирование кодов Рида-Соломона с использованием модифицированной техники вылавливания ошибок [Текст] / С.И.Егоров // Цифровая обработка сигналов и ее применение: матер. 7-ой Междунар. конф. Москва, 2005. С. 112-116.

29. Егоров, С.И. Помехоустойчивое определение фаз последовательностей n-грамм m-последовательностей путем декодирования с вылавливанием ошибок [Текст] / С.И.Егоров // Труды 60-ой научной сессии, посвященной дню радио. Москва, 2005. Том 2, С. 239-241.

30. Егоров, С.И. Декодер кодов Рида-Соломона для телекоммуникационных систем, увеличивающий энергетический выигрыш от кодирования [Текст] / С.И.Егоров // Телекоммуникационные технологии и сети: сб. науч. трудов 2-го международного радиоэлектронного форума.

Харьков, 2005. Том 4, С. IV.189-131. Егоров, С.И. Повышение эффективности применения кодов РидаСоломона в телекоммуникационных системах [Текст] / С.И.Егоров // Цифровая обработка сигналов и ее применение: матер. 8-ой Междунар. конф.

Москва, 2006. С. 53-57.

32. Егоров, С.И. Применение декодирования с вылавливанием ошибок для помехоустойчивого определения фаз последовательностей n-грамм // Математическое и программное обеспечение вычислительных систем:

межвуз. сб. науч. тр./ под ред. А.Н.Пылькина. М.: Горячая линия - Телеком, 2006. С. 13-19.

33. Егоров, С.И. Повышение эффективности коррекции ошибок помехоустойчивыми кодами Рида-Соломона с использованием информации о надежности символов [Текст] / С.И.Егоров, С.Р.Ломтадзе // Современные проблемы информатизации в моделировании и анализе сложных систем: сб.

трудов. / под ред. д-ра техн. наук., проф. О.Я. Кравца. Вып. 12. Воронеж:

Научная книга, 2007. С. 161-163.

34. Егоров, С.И. Коррекция ошибок синхронизации в каналах со вставками/ выпадениями символов с использованием М-последовательности [Текст] / С.И.Егоров // Цифровая обработка сигналов и ее применение: матер.

9-ой Междунар. конф. Москва, 2007. С. 31-34.

35. Егоров, С.И. Процедура и устройство коррекции ошибок синхронизации в каналах со вставками/ выпадениями символов [Текст] / С.И.Егоров // Математическое и программное обеспечение вычислительных систем: межвуз. сб. науч. тр./ под ред. А.Н.Пылькина. М.: Горячая линия - Телеком, 2007. С. 4-13.

36. Егоров, С.И. Использование мягких решений при декодировании кодов Рида-Соломона [Текст] / С.И.Егоров, С.Р.Ломтадзе // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций:

матер. 15-ой Междунар. науч.-техн. конф. Рязань: Рязанская гос. радиотехн.

ун-тет, 2008. С. 83-85.

37. Егоров, С.И. Повышение эффективности декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния с использованием мягких решений [Текст] / С.И.Егоров // Цифровая обработка сигналов и ее применение: матер. 10-ой Междунар. конф. Москва, 2008. С.

37-40.

38. Егоров, С.И. Использование мягких решений при декодировании кодов Рида-Соломона за границей половины минимального кодового расстояния [Текст] / С.И.Егоров, С.Р.Ломтадзе // Оптико-электронные приборы и устройства в системах распознавания образов, обраб. изображ. и символьной информ.: матер. 8-ой Междунар. науч.-техн. конф. Курск:

Курский гос. техн. ун-т, 2008. С. 144-146.

39. Егоров, С.И. Пошаговое декодирование выколотых кодов РидаСоломона методом восстановления выколотых символов [Текст] / С.И.Егоров // Математическое и программное обеспечение вычислительных систем: межвуз. сб. науч. тр./ под ред. А.Н.Пылькина. М.: Горячая линия - Телеком, 2008. С. 9-16.

40. Егоров, С.И. Декодирование кодов Рида-Соломона за границей половины минимального кодового расстояния с использованием мягких решений [Текст] / С.И.Егоров // Информационные технологии моделирования и управления. 2008. №9 (52). С. 1039-1044.

41. Егоров, С.И. О корректирующих возможностях декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния [Текст] / С.И.Егоров, О.Б.Графов, Д.Г.Барышок // Современные проблемы информатизации в анализе и синтезе программных и телекоммуникационных систем: сб. трудов. / под ред. д-ра техн. наук., проф.

О.Я. Кравца. Вып. 14. Воронеж: Научная книга, 2009. С. 306-308.

42. Егоров, С.И. Алгоритм декодирования кодов Рида-Соломона, исправляющий дополнительные ошибки за пределами половины минимального кодового расстояния [Текст] / С.И.Егоров // Методы и алгоритмы прикладной математики в технике, медицине и экономики: матер.

9-ой Междунар. науч.-практ. конф. Новочеркасск: ЮРГТУ, 2009. С. 16-19.

43. Егоров, С.И. Алгоритм декодирования кодов Рида-Соломона, исправляющий вплоть до n-k ошибок в кодовом слове [Текст] / С.И.Егоров // Цифровая обработка сигналов и ее применение: матер. 11-ой Междунар.

конф. Москва, 2009. С. 27-30.

44. Егоров, С.И. Списочное декодирование кодов Рида-Соломона с величиной радиуса вплоть до n-k [Текст] / С.И.Егоров // Информационноизмерительные, диагностические и управляющие системы: матер. Междунар.

науч.-техн. конф. Курск: Курский гос. техн. ун-т, 2009. С. 37-40.

45. Егоров, С.И. Алгоритм декодирования кодов Рида-Соломона, исправляющий несколько ошибок за границей половины минимального кодового расстояния [Текст] / С.И.Егоров // Информационные технологии моделирования и управления. 2009. №2 (54). С.250-255.

Изобретения 46. А.с. 1092510 СССР, МКИ G 06 F 11/12. Устройство цикловой синхронизации для внешней памяти [Текст] / Типикин А.П., Добрянский П.Е., Егоров С.И. (СССР). № 3559993/18-24; заявл. 28.02.83; опубл. 15.05.84, Бюл. № 18. 6 с.

47. А.с. 1254457 СССР, МКИ G 06 F 1/04. Устройство для синхронизации внешних блоков памяти [Текст] / Типикин А.П., Добрянский П.Е., Егоров С.И., Петров В.В. (СССР). № 3851468/24-24; заявл. 01.02.85;

опубл. 30.08.86, Бюл. № 32. 6 с.

48. А.с. 1656689 СССР, МКИ H 03 M 13/00, 13/02. Устройство кодирования и вычисления синдромов помехоустойчивых кодов для коррекции ошибок во внешней памяти ЭВМ [Текст] / Егоров С.И., Типикин А.П., Петров В.В., Гостев А.В. (СССР). №4722202/24; заявл. 26.06.89; опубл.

15.06.1991, Бюл. № 22, 7 с.

49. Пат. 2024966 РФ, МКИ G11B 27/10, 20/18. Устройство для определения начала блока данных во внешней памяти [Текст] / Максимов О.А., Егоров С.И., Типикин А.П., Вачевских А.С., Лукибанов В.М. (Россия).

№ 5022512/10; заявл. 02.07.91; опубл. 15.12.94, Бюл. № 23, 12 с.

50. Пат. 2137320 РФ, МПК H 04 N 7/087, H 04 J 3/06. Устройство приема информации из канала [Текст] / Егоров С.И., Бессонов Д.П. (Россия).

№98111331/09; заявл. 11.06.98; опубл. 10.09.1999, Бюл. № 25, 17 с.

51. Пат. 2192038 РФ, МПК G 06 F 11/00, G 08 C 25/00. Устройство измерения параметров ошибок в канале [Текст] / Егоров С.И., Глухарев И.Н., Типикин А.П. (Россия). №2001119781/09; заявл. 16.07.2001; опубл.

27.10.2002, Бюл. № 30, 36 с.

52. Пат. 2224282 РФ, МПК G 06 F 11/00, H 04 B 17/00. Устройство исправления ошибок синхронизации в потоке данных [Текст] / Егоров С.И., Проценко А.М., Титов В.С. (Россия). №2002113975/09; заявл. 28.05.2002;

опубл. 20.02.2004, Бюл. № 5, 51 с.

53. Пат. 2314639 РФ, МПК H 03 M 13/00. Устройство декодирования кодов Рида-Соломона [Текст] / Егоров С.И. (Россия). №2006110814/09; заявл.

03.04.2006; опубл. 10.01.2008, Бюл. № 1, 20 с.

Соискатель С.И. Егоров Подписано в печать ______________. Формат 6084 1/16.

Печатных листов _______. Тираж 100 экз. Заказ ______.

Курский государственный технический университет, 305040, Курск, ул. 50 лет Октября, 94.

Авторефераты по всем темам >> Авторефераты по техническим специальностям

Blog

МЕТОДЫ, АЛГОРИТМЫ И УСТРОЙСТВА КОРРЕКЦИИ АДДИТИВНЫХ И СИНХРОНИЗАЦИОННЫХ ОШИБОК ВО ВНЕШНИХ ЗАПОМИНАЮЩИХ УСТРОЙСТВАХ ЭВМ