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

003485330

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

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

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

2 6 НОЯ 2009

КУРСК 2009

003485330

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

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

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

доктор технических наук, профессор, заслуженный деятель науки РФ

Бурковский Виктор Леонидович доктор технических наук, Левин Илья Израилевич

доктор технических наук, профессор, заслуженный деятель науки РФ

Сизов Александр Семенович

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

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

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

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

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

Ученый секретарь диссертационного совета

Автореферат разослан «/0 » 2009 г.

кандидат техн. наук, доцент

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

s

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.

Публикации. Результаты диссертационной работы отражены в 71 печатной работе, в том числе одной монографии, 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 таблиц.

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

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

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

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

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

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

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

Ae-AW/b,

где: А^бп - количество информации (в битах) пользователя в блоке данных и Рев - вероятность сбоя в блоке. Для ВЗУ ЭВМ N5 должна быть не менее 10121015 бит в зависимости от назначения информации.

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

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

где а - примитивный элемент поля CF(#), b -целочисленная константа. Число гарантированно исправляемых ошибок PC-кодом tc = —^- .

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

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

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

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

где У^ко (бит/такт) - пропускная способность УКО (время измеряется в

тактах), Хв ~ число вентилей и Хп - число бит памяти, необходимых для реализации УКО. Удельная пропускная способность зависит от используемых алгоритмов коррекции ошибок и качества синтеза УКО, определяющих вычислительную и аппаратную сложность УКО. Частными показателями являются вычислительная сложность алгоритма коррекции ошибок и задержка декодирования (коррекции ошибок).

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

Число исправляемых ошибочных символов в кодовом слове ограничено для классической алгебраической процедуры синдромного

d-\

. В конце 80-х годов прошлого

декодирования PC-кодов величиной tc = ^

века Блейхут рассмотрел возможность исправления tc+1 ошибочного символа с помощью аналитического продолжения алгоритма Берлекэмпа-Месси еще на две итерации. Он предложил искать две дополнительные неизвестные невязки и позиции 4-+1 ошибочных символов с помощью построения гистограмм.

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

Теорема 2.1: Пусть полином локаторов ошибок Л(2'с)(х), вспомогательный полином и формальная степень полинома

локаторов Ly получены после 2t с итераций алгоритма Берлекэмпа-Месси. Если Ьг,с < tc или L2Ic > tc +1, то тогда в принятом слове не может быть tc +1 ошибок.

Если Llk =tc, то тогда неизвестные невязки А2,с+1 и Д2,с+2,

соответствующие tc +1 ошибкам, могут быть найдены из следующей системы уравнений:

Д2,с+2 =(«'-С(-Л2,с+1)-Д2,с+,,М), 1,..., я-1, если A(2fc)(«")*0, (1)

где

С,=Я(2'с)(«~')/Л<2'с)(0"'). (2)

Если ¿2,с = tc +1, то тогда невязки могут быть найдены из системы: Ä2,c+2 = А-a?-Ä2,c+i,/=0, 1.....и-1, если (3)

где

D, =A(2t)(0/(5<2'c)(«~')-«"2'). (4)

Следствие 2.1: Примем: Р(х)= \а'с}(х), если ¿2,с = /с, и Р(х)= В{2'с)(х), если Ьг,с = tc +1.

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

£ = {¿iU «= U = i+1.....n-\;P(aJ) ф 0}; i = 0,...,и-1- tc\ Р(ач) ф 0. (5)

Если ¿2,с= tc +1, то последовательности значений Д2гс+ь полученные из системы (3), будут иметь следующий вид:

S, = {A'iU = U = 1+1,...,«-1; P(aJ) Ф0}-, i = 0.....n-l- tc, Р(а') ф 0. (6)

с а -а'

Утверждение 2.1: Пусть А - множество значений А2,с+1 такое, что

полином Л(2'с+2)(х) имеет точно te +1 допустимых корней в поле GF(í/). Пусть Wj = Cnt[S¡); / = 0,..., n-l-tc, Р(о.~') Ф 0. Тогда множество Д состоит из всех значений а', удовлетворяющих условию - íc для всех i = 0,...,n-\-tc, Р(оГ') ^ 0 и /= 0,...,<¡r-2.

Сущность предложенного метода поиска неизвестных невязок заключается в вычислении последовательностей S¡ возможных значений ^2tc+¡ невязки по формулам (5) или (6) и подсчете одинаковых

значений невязок для каждой последовательности. Значения невязок, найденные в последовательности 5, ровно te раз, являются искомыми.

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

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

2. Вычисление с использованием алгоритма Берлекэмпа-Месси многочлена локаторов ошибок Л<2'с)(л:) и вспомогательного многочлена В{2'с>(х).

3. Вычисление преобразования Фурье многочленов Л(2'с)(лг) и В(2'с)(х).

4. Вычисление коэффициентов Q (2), если Lltc =tc, или D¡ (4), если L2,c =tc+1.

5. Вычисление последовательностей S¡ возможных значений невязки

^2ic+i (5 или 6) для / = 0,..., n-\-tc, удовлетворяющих условию P(cl') Ф 0.

Вычисление W¡ и поиск всех al, удовлетворяющих wu = 1С для всех i = 0,...,n-Uo Р( а') ^ 0 и / = 0,...,q-2.

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

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

Показано, что число итераций поиска невязки A2ic+i равняется (п-

\Mc){n-tc)¡2. Для высокоскоростных PC-кодов (и»/с) это число близко к п2/2. Быстродействие предложенного метода поиска невязок в 2{q-\)n'({n-\ ( tc){n-tc)) раз выше быстродействия метода поиска невязок Блейхута. Для высокоскоростных PC-кодов выигрыш по быстродействию составит 2(q-\)/n раз.

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

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

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

Таблица 1.

Процент исправляемых конфигураций ошибок веса /с+1

п

30 55 80 105 130 155 180 205 230 255

7 67,7 0,5 0,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,0

d 11 99,9 99,3 93,5 70,4 25,5 1,7 0,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,0

15 100,0 100,0 100,0 99,9 99,5 97,8 92,6 80,1 55,9 26,1

17 шоТо1 100,0 100,0 100,0 100,0 99,9 99,5 98,1 94,8 86,8

Таблица 2.

Зависимость степени увеличения числа принятых бит на сбой е.у от длины

слова РС-кода

п

30 55 80 105 130 155 180 205 230 255

7 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,0

15 51,2 Г 23,7 15,5 11,5 9,2 6,8 4,6 2,9 1,8 1,2

17 59,2 26,8 18,0 13,3 10,0 8,5 7,1 5,8 4,4 3,3

* - моделирование не проводилось

В таблице 2 показана зависимость степени увеличения числа принятых бит на сбой Ejv =aV/A'6° от длины слова п PC-кода для случая исправления одного дополнительного ошибочного символа при вероятности битовых ошибок в канале Pso =Ю'3. и Ы£ - количество принятых бит на сбой в случаях исправления (с +1 и <с ошибок соответственно.

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

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

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

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

процедура позволяет значительно расширить область эффективного применения алгоритма декодирования относительно п. Так, для РС-кода с ii=13, определенного над конечным полем GF(28), эта область увеличилась примерно в два раза. Длина слова и, при которой наблюдается увеличение основного интегрального показателя Л'5 эффективности коррекции ошибок в четыре раза, достигла величины 255 символов по сравнению со 140 символами (см. табл. 2).

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

аШ1 _ аип

S, = {лу#т = 7--;j=i+l,...,n-l; Р(оГ'т)фО }; i= 0 ,...,ис; P(am^Q,

или

5,={ = Dam~_DaLàn -J = .....«-1; / Vя* 0 };/ = 0,...,Пс,

где L - массив номеров позиций символов принятого кодового слова, упорядоченных по возрастанию надежности символов; пс< пЛ-tc- При такой организации перебора неизвестная невязка ^2fc+i находится при малых

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

Результаты исследования времени поиска неизвестных невязок, управляемого надежностью символов, в канале с аддитивным белым гауссовским шумом и модуляцией BPSK приведены на рис. 1. Путем имитационного моделирования исследовались РС-коды с d= 13, определенные над конечным полем GF(28), пс = 30. На графике Ç обозначает коэффициент уменьшения времени поиска неизвестных невязок, равный отношению произведения ng-nw (где п„ - число обработанных кодовых слов в процессе моделирования; ns - (и-1+<с)(п-гс)/2) к действительному числу вычислений невязок A'i^+i декодером при обработке п№ слов. Зависимость 1 соответствует случаю декодирования кодовых слов с te +1 ошибкой без управления (характеризует возможность повышения быстродействия декодера за счет усреднения времени декодирования), зависимость 2 -случаю управления поиском позиций ошибок информацией о надежности принятых символов.

100 150 200 250

п

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

Из графика видно, что выигрыш во времени поиска при управляемом декодировании составляет примерно два порядка.

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

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

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

Утверждение 2.2: Если Llt_ =tc, то последовательности значений

A'^+i = 'а'. полученные для пар i и j = i+k уравнений (1), будут иметь вид:

S, = {А"2'*+1 - (С, - См) • (1 -а" У; к = 1,...,«-Ы;

Р(а**) ¿0},/ = 0,..., п-ис, Р(а')Ф 0. (7)

Если L2,c=tc +1, то последовательности значений A'^+i = A'^+i а', полученные из (3), будут иметь вид:

S, = {Д«£+1 = (D, - DM) • (1 -аку\к =

Р(а'-к) * 0 },/= 0,..., п-Uc, Р(а) Ф 0. (8)

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

расстояния

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

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

• ха-

Кед

О*

-

Inv

СикЩ+к) С, (Я,)

Кед

1

Иед

1 А"'* J_ Jy 21+1

1-а'

Яед

X Count

1 /V 2/+1

1 -а*-

X Count

1

1 Qy-

Reg

1 - а*"2 I 1

X Count

Рис. 3. Структурная схема блока поиска невязок и ошибок с параллельной организацией поиска невязок

Разработанный в работе метод предполагает вычисление V - |.у| ((.? = /с -¿2,с) наборов последовательностей .....возможных значений невязки

Д'1''2"'''для всех возможных наборов индексов /1( /2,...,/н ('/= 1м+1,...,и-1, / =

2у) и выделение значений переменной Д, которые встречаются точно м> = ¡с +1-у раз в какой-то из этих последовательностей, где

4*2.....U~{A ~ F°2(i i i R R R )" -,'-1+1'и 1}'

'м = '/-г +1, я - 1 - w,-. гj = ij-1 — w — / + j,..., i, = 0, n - w - / +1

(9)

AM Л <Л<-</.

V(tl,*2> V(4U2) M

й<*2 il<*2

о1 = V - |я+1| и о2 = V - для первого набора 1, для последующих

наборов о 1 и о2 декрементируются;

( а(25+,)'й(2'с)(а")/А(2,с)(«"'),если5 >0 [а^и-1)'А{2'с\а"')/В(2'с)(а~'), в противном случае' (Если V = -5 вычисляется один набор.)

Если найдены значения переменной Л, которые встречаются точно м' раз в какой-то из этих последовательностей, то значениями локаторов ошибок являются значения индексов /ь 1г,...,цл этой последовательности и множество значений последнего индекса ¡¡, соответствующего таким значениям переменной А.

Асимптотическая сложность разработанного алгоритма списочного декодирования растет полиномиально относительно п для фиксированного 1к. Для малых значений 1е сложность растет значительно медленнее в сравнении с алгоритмом Гурусвами -Судана (ОБ-алгоритмом).

Гистограмма рис. 4 характеризует корректирующую способность РС-кодов с ¿/=17, определенных над полем ОР(28), при их декодировании алгоритмами, не использующими мягкие решения. Радиус декодирования /т:,х соответствует случаю, когда на выходе списочного декодера преобладают (не менее 80%) списки с не более чем одной конфигурацией ошибок (ряд 1). Также на гистограмме приведено число ошибок к^, которые можно исправить с помощью вв-алгоритма (ряд 2) и число гарантированно исправляемых РС-кодом ошибок /с (РЯД 3).

12,00 10,00 8,00 t 6,00 4,00 2,00 0,00

I i i ш

II 1:1

lllil llliiS

I I

I I

II

itit

II i t lililí

55 80 1 05 1 30 155 180 205 230 255

Рис. 4. Исправляющая способность различных алгоритмов декодирования РС-кодов над ОБ(28) с ¿=17

Разработанный алгоритм списочного декодирования позволяет исправлять tmax ошибок. Из гистограммы следует, что алгоритм Гурусвами-Судана не эффективен для высокоскоростных кодов при п - 105,...,255, где tas = к, да и для кодов с меньшими скоростями не использует всех их потенциальных корректирующих возможностей, так как tos < tmах.

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

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

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

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

<?/& Ф Ч/ёр ?/(&«') Ф «/(а«')-

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

?/=Я/а'(а<+а/И^''&а'(а'+а')+ф"'&а'(а/+а')], 1=0,.,(1-2; I * у гДе 8(х) = П (* ~ а')= = 2.8■

)=ь+\ (х-а ) у=о

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

д^аХа'+а!) + д/'даЦа'+а) + д,-1т'(а'+а!) = 0. (10)

где ф, , ф - произвольно выбранные коэффициенты полинома остатка <з>(х).

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

Следствие 3.2. Если в первых п-1 символах кодового слова РС-кода произошло I ошибок (/<<<(/-2), то следующая система уравнений не может выполняться:

цф о,

Я/Е, Ф ЧМ й/(8>а') Ф чМр1), (11)

где (и j любые ненулевые не равные друг другу целые числа меньшие с1-\.

Предлагаемый метод пошагового исправления ошибок подразумевает исправление ошибки в одном фиксированном проверочном символе Г/ слова РС-кода. Значение ошибки для этого проверочного символа представляет собой функцию от д(х): У=Лд(х)). После выполнения циклического сдвига определяют значение ошибки для следующего символа кодового слова. Процедура повторяется до тех пор, пока не будут обработаны все символы. Декодирование с неполным вылавливанием ошибок возможно при обнаружении фиксированного числа ошибок, оставшихся в области информационных символов, и учете их влияния на компонент синдрома д,. Это обеспечивается использованием Теоремы 3.1. и ее следствий.

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

1. Вычисление многочлена синдрома := Кея0(1)[г(х)-х(2 "+0]. 2.7 := «-1.

0, если = 0

. если 0 < Ш(д(х)) < 2

3 ^ =/(?(*)) = 1 _ ,/ / лч о „пч

0, если ■wt(д{x)) > 2 и (10) не выполняется > д0-дт0, если м-7(<у(х)) > 2 и (10) выполняется

где <7«о1 а1) + д/'^^а'+а0)], г, I в (10) принимают

значения 3, 2,1 в любом порядке

4. г, - - гI — У.

5. ^(дг):=Ке5С(1)[^(х)-д: ].

6.У:=/-1.

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

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

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

вентилей

Самый сложный блок пошагового декодера - блок вычисления значений цтй и цт\ содержит только 2 сумматора, 5 умножителей на постоянные коэффициенты и 4 инвертора в конечном поле Галуа. Удельная пропускная способность разработанного декодера возросла в сравнении с лучшим из известных пошаговых декодеров с такой же корректирующей способностью по параметру в еХ1=2,3 раза, по %2 в ^2=1,3 раза (ш=8).

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

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

О, если ы(д(х)) - О д0, если 0 < м1(д(х)) < 2 /(?(•*)) = ■{ О, если \\И(ц(хУ) > 2 и (11) не выполняется

<?„- Яо« V + а'т'^а^а0 +сс') + V V +<**)1,

если м'1(д(х)) > 2 и (11) выполняется

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

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

ВхД

х(&.]а'" Г'

53

в Л КЛУ ОГ

с* Ыс ьп А) то 1

и 22

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

коррекции

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

Сложность комбинационно-логической схемы вычисления Г разработанного декодера определяется следующим образом: Хд-(25г-23)т+2/-+83 и у^=г2"'-т. При реализации вычислений над полем ОР(28)

декодер может корректировать ошибки в потоке данных, передаваемых со скоростью 1 Гбит/с, при работе на тактовой частоте 250 МГц. Параметры удельной пропускной способности декодера: ~ З,610"3, Хг= 3,3-10"4 (г=6).

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

Г 0,еслии>/(<7(х))<1

д" +а')/[д;^1а'(аг +а})+д^)а'{ар +a')\,ecлvíwt(q(x))>\,

где р - количество выколотых символов.

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

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

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

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

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

' вт-1 ¡¡¡+т-1 + От-2 + — + а0 ^ ,

где коэффициенты я/ принимают значения из двоичного поля. Период такой последовательности равен п = 2т-1. Сегмент М-последовательности, состоящий из / следующих подряд символов, называется /-граммой. Важными частными случаями /-граммы являются «-грамма (/=«) и т-грамма (/=/л). По любой /я-грамме можно восстановить всю М-последовательность.

В работе под фазой <р данной /-граммы понимается ее расположение в М-последовательности с неоднозначностью к-п {к - целое):

(p = imoAnt

где / - индекс первого элемента /-граммы ($/) в М-последовательности. Любые фиксированные т бит /-граммы однозначно определяют ее

фазу. Значение фазы удобно вычислять как табличную функцию от

последовательности символов m-граммы, расположенной в определенном месте /-граммы.

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

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

Вставленная в данные М-последовательность разбивает поток символов на группы из р символов. Назовем последовательность из /символов, выбранную из потока данных в канале с периодом р, /-группой (г,, r,ip, ..., г,»(/_|)р). Определим следующим образом фазу /-группы:

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

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

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

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

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

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

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

1./.=0. ..

2. Rr:= shift(/?r,/>); Rt := shift(/?,,r,.x).

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

4. Нахождение оценок фазы y/'i r, фазы <рг /-граммы с достоверностью 0Г для Rr. Нахождение оценок фазы , фазы <pi /-граммы с достоверностью в/ для R,.

5..Если 0г >в>, то (f, г := ^ и £*:= <рг\ в противном случае ц/,,_f := ^ ^ и L*:= <pi.

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

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

8. RAM(L*) := (r,.„r(+bt,...,r,+p.i.t).

9.t:=t +1.

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

В описании алгоритма используются следующие обозначения: t - номер последнего символа, поступившего на вход устройства коррекции ошибок синхронизации;

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

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

Ri~ строка, содержащая символы левых окрестностей символа г,.т;

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

удаляется, элемент г помещается на место левого элемента;

(рг и <pi - оценки фаз наиболее достоверных /- грамм правых и левых

окрестностей символа /ут;

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

Ц>'г1т и - оценки справа и слева фазы символа r,.z относительно М-

последовательности;

tyг,_г - итоговая оценка фазы символа г,.г\

L* - оценка локатора группы данных с первым символом (значения L* и ^ г определяют расположение группы данных в потоке); RAM - массив, в который записываются группы данных (г,.„ г,+).х,..., r,+p.i.t) (представляет в алгоритме буферное ОЗУ).

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

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

Входные

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

Фаза /-граммы может быть определена по значению любой входящей в нее в известном месте т-граммы:

<р = (<р„-Л тодп , (13)

где <рт - фаза ти-граммы, смещение «-граммы относительно начала I-граммы (/-=0,.. ,,1-т). Однако для повышения помехоустойчивости необходимо определять фазу, используя все символы /-граммы.

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

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

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

где L{ ) - табличная функция, дающая фазу m-граммы в зависимости от ее содержания; B{t) - целочисленная функция, значение которой инкрементируется по модулю и после обработки каждых р символов pJ+A^)mod«, К - целочисленная константа; R, - относительная фаза m-граммы. Тогда

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

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

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

Таблица 3.

Зависимость степени увеличения числа принятых бит на сбой en от

параметра группирования g

S

0,2 0,4 0,6 0,8

Lrp 3 6,3 72,4 540,4 5504

12 1,8 2,1 7,0 1099

Устройство обрабатывает один входящий символ за 10 тактов, что позволяет при реализации его на современных ПЛИС с тактовой частотой 200-500 МГц обеспечить пропускную способность 20-50 Мбит/с при параметрах удельной пропускной способности: XI = 2.2-10'5, у^ = 1.8-10"6.

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

основанного на интерпретации и-грамм в качестве слов кода максимальной длины.

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

Теорема 4.1\ Пусть v,(x) и У/м(лг) обозначают слова циклического кода, соответствующие двум соседним (сдвинутые на один символ) »-граммам, принятым из канала:

V,(x) = V, у'1 + vy+i х?~2+ ... + Ví+n-2 х + v/+„.|, VihM = V/+1 У"1 + v,42x""2 + ... + Wi * + v/+„, v, = Si + e¡,

где s¡ - символ /«-последовательности и e¡ - соответствующий ему символ ошибки. Пусть q,{x) - синдром кодового слова v,{*):

q,{х) = RessM(v,(x)),

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

Тогда синдром q,n(x) кодового слова v/+i(x) может быть получен из синдрома q,{x) кодового слова v,(x) следующим образом:

ql+i(x) = Res^x)(q,{x)x) + (v/+„-V/).

Процедуру определения фаз для первой последовательности и-грамм можно описать следующим образом. При вычислении фазы следующей л-граммы осуществляется одна итерация деления многочлена q¡{x), умноженного на х, на порождающий многочлен g(x). При этом одновременно прибавляется к свободному члену многочлена остатка сумма по модулю 2 входящего в и-грамму символа v¡+„ и выходящего из нее символа vt. Если вес получившегося многочлена остатка q¡+i(x) меньше порога t, это значит, что многочлен q¡-\(x) содержит конфигурацию ошибок, которая может быть исправлена. В этом случае к символам опорной т-rpаммы, соответствующим последним символам «-граммы, прибавляются значения т младших коэффициентов многочлена qi+i(x). Исправленная опорная т-грамма используется в качестве аргумента табличной функции для получения значения фазы. Вес многочлена c7/+i(.x) дает оценку надежности определения фазы.

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

Теорема 4.2: Пусть Rev(p(x)) обозначает многочлен возвратный к многочлену р(х). Тогда /«-модифицированным синдром qmi.\(x) кодового

слова может быть получен из »»-модифицированного синдрома д"\(х)

кодового слова у,{дг) следующим образом:

дтм(х) = /^(«А*)-*) + (у„я-л>,)Нечфез эГ1)). (14)

Процедура определения фаз для второй последовательности «-грамм выполняется аналогично процедуре для первой последовательности с небольшими отличиями. Во-первых, при итеративном вычислении синдромов используется константный корректирующий многочлен Яех(Ке$ кетШ) (*"')) (14), который прибавляется к многочлену </",(х) х , если у,+„ ^ V,. Во-вторых, к символам опорной т-граммы прибавляются значения т старших, а не младших коэффициентов многочлена д™+1(х), поскольку в этом случае опорная т-грамма находится в начале и-граммы.

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

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

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

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

Таблица 4.

Достигнутые показатели эффективности коррекции ошибок

Алгоритмы Аппаратные средства

Алгоритм Алгоритм Алгоритм Блок по- Пошаго- УКОС УКОС

декодиро- списочно- исправле- иска не- вый де- (мажор. (опред.

вания РС- го деко- ния оши- вязок и кодер метод фаз с

кодов с дирова- бок син- позиций РС- опред. исполь-

исправле- ния РС- хрониза- ошибок кодов фаз) зовани-

нием ¿с+1 кодов ции РС-де- ем М-

ошибок кодера кодов)

б(1/=3+13 число л- 5 3,8-10"5, Х.= 2,2-10 , х.= 8,2-10"5,

исправл. ошибок ел=2-г7 Х2= 1,4-10"5 Б*,=2,3, 1,8-10"6 Х2= „ 1,6-10

Сложность Щп-к) Ед=100,

0( и2) £¿2=100 мяг.реш.

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

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

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

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

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

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

удельная пропускная способность декодера при использовании этого метода увеличивается примерно на два порядка.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

СПИСОК ОСНОВНЫХ ПУБЛИКАЦИЙ

Монография

1. Егоров, С.И. Коррекция ошибок в информационных каналах периферийных устройств ЭВМ [Текст]: монография / С.И.Егоров; Курск, гос. техн. ун-т. Курск, 2008.252 с.

Статьи в журналах, входящих в перечень ВАК РФ

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

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

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

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

6. Глухарев, И.Н. Корреляционный и локаторный методы измерения параметров ошибок синхронизации в цифровых каналах передачи информации информации [Текст] / И.Н.Глухарев, С.И.Егоров, А.П.Типикин // Телекоммуникации. 2003. №12. С. 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 Comtnun, Vol. 52, № 12. 2004, P. 2052-2056.

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

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

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

11. Егоров, С.И. Помехоустойчивое определение фаз и-грамм М-последовательности [Текст] / С.И.Егоров // Известия ВУЗов. Сер. Приборостроение. 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+\ 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. Егоров, С.И. Исправления ошибок типа вставок/выпадений бит в каналах передачи цифровой информации [Текст] / С.И.Егоров, A.M. Проценко // Оптико-электронные приборы и устройства в системах распознавания образов, обраб. изображ. и символьной информ.: матер. 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. Егоров, С.И. Исправление ошибок синхронизации в каналах передачи данных путем декодирования М-кодов [Текст] / С.И.Егоров, А.М.Проценко // Оптико-электронные приборы и устройства в системах распознавания образов, обраб. изображ. и символьной информ.: матер. 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. Егоров, С.И. Помехоустойчивое определение фаз последовательностей «-грамм /и-последовательностей путем декодирования с вылавливанием ошибок [Текст] / С.И.Егоров // Труды 60-ой Научной сессии, посвященной дню радио. Москва, 2005. Том 2, С. 239-241.

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

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

32. Егоров, С.И. Применение декодирования с вылавливанием ошибок для помехоустойчивого определения фаз последовательностей «-грамм // Математическое и программное обеспечение вычислительных систем: межвуз. сб. науч. тр./ под ред. А.Н.Пылькина. М.: Горячая линия - Телеком, 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. Егоров, С.И. Алгоритм декодирования кодов Рида-Соломона, исправляющий вплоть до п-к ошибок в кодовом слове [Текст] / С.И.Егоров // Цифровая обработка сигналов и ее применение: матер. 11-ой Междунар. конф. Москва, 2009. С. 27-30.

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

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

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

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

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

49. Пат. 2024966 РФ, МКИ5 G11B 27/10, 20/18. Устройство для определения начала блока данных во внешней памяти [Текст] / Максимов O.A., Егоров С.И., Типикин А.П., Вачевских A.C., Лукибанов В.М. (Россия). № 5022512/10; заявл. 02.07.91; опубл. 15.12.94, Бюл. № 23, 12 с.

50. Пат. 2137320 РФ, МПК6 Н 04 N 7/087, Н 04 J 3/06. Устройство приема информации из канала [Текст] / Егоров С.И., Бессонов Д.П. (Россия). №98111331/09; заявл. 11.06.98; опубл. 10.09.1999, Бюл. №25,17 с.

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

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

53. Пат. 2314639 РФ, МПК7 Н 03 М 13/00. Устройство декодирования кодов Рида-Соломона [Текст] / Егоров С.И. (Россия). №2006110814/09; заявл. 03.04.2006; опубл. 10.01.2008, Бюл. № 1,20 с.

Изобретения

Соискатель

Подписано в печать 3.1-40 .ЪООв. Формат 60x84 1/16 . Печатных листов О Тираж 100 экз. Заказ 6 & . Курский государственный технический университет, 305040, Курск, ул. 50 лет Октября, 94.

С.И. Егоров

УКАЗАТЕЛЬ СОКРАЩЕНИЙ И ПРИНЯТЫХ УСЛОВНЫХ ОБОЗНАЧЕНИЙ.

ВВЕДЕНИЕ.

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

1.1. Классификация ошибок в информационных каналах внешних запоминающих устройств ЭВМ.

1.2. Характеристики ошибок во внешних запоминающих устройствах ЭВМ.

1.3. Методы защиты от ошибок в информационных каналах внешних запоминающих устройств ЭВМ.

1.4. Применение кодов Рида - Соломона для коррекции ошибок.

1.5. Методы защиты от ошибок синхронизации в информационных каналах внешних запоминающих устройств ЭВМ.

1.6. Аппаратные средства защиты от ошибок информационных каналов внешних запоминающих устройств ЭВМ.

1.7. Выводы.

2. СИНДРОМНОЕ ДЕКОДИРОВАНИЕ КОДОВ РИДА-СОЛОМОНА ЗА ГРАНИЦЕЙ ПОЛОВИНЫ МИНИМАЛЬНОГО КОДОВОГО РАССТОЯНИЯ.

2.1. Классическая процедура синдромного алгебраического декодирования кодов Рида-Соломона.

2.1.1. Математическое обоснование процедуры декодирования.

2.1.2. Критерии сложности для оценки процедуры декодирования.

2.1.3. Основные этапы выполнения процедуры декодирования.

2.1.4. Оценки сложности процедуры декодирования.

2.2. Исправление дополнительного ошибочного символа в кодах Рида

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

2.2.1. Процедура исправления tc+1 ошибочных символов.

2.2.2. Метод поиска неизвестных невязок аналитического продолжения алгоритма Берлекэмпа-Месси на две итерации.

2.2.3. Алгоритм исправления tc+l ошибочных символов.

2.2.4. Структурно-функциональная организация декодера, исправляющего /¿+1 ошибочных символов.

2.2.5. Выигрыш от исправления tc+1 ошибочных символов.

2.2.6. Использование мягких решений.

2.3. Списочное декодирование кодов Рида-Соломона с величиной радиуса вплоть до п-к.

2.3.1. Метод определения позиций ошибочных символов в коде Рида

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

2.3.2. Алгоритм списочного декодирования кодов Рида-Соломона с величиной радиуса вплоть до п-к.

2.3.3. Корректирующие возможности кода Рида-Соломона, реализуемые алгоритмом.

2.4. Выводы.

3. ДЕКОДИРОВАНИЕ КОДОВ РИДА-СОЛОМОНА НА ОСНОВЕ

НЕПОЛНОГО ВЫЛАВЛИВАНИЯ ОШИБОК.

3.1. Классическая техника вылавливания ошибок для декодирования циклических кодов.

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

3.3. Пошаговое декодирование кодов Рида-Соломона на основе неполного вылавливания ошибок.

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

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

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

3.4. Пошаговое декодирование выколотых кодов Рида-Соломона.

3.4.1. Особенности применения выколотых кодов Рида-Соломона в оптических накопителях информации.

3.4.2. Вычисление синдромов для выколотых кодов Рида-Соломона.

3.4.3. Пошаговое декодирование с исключением выколотых символов.

3.4.4. Пошаговое декодирование с восстановлением выколотых символов.

3.4.5. Структурно-функциональная организация комбинированного

ВЗЛО пошагового декодера выколотых кодов Рида-Соломона.

3.5. Выводы.

4. КОРРЕКЦИЯ ВСТАВОК/ВЫПАДЕНИЙ СИМВОЛОВ В БЛОКАХ

ДАННЫХ С ИСПОЛЬЗОВАНИЕМ М-ПОСЛЕДОВАТЕЛЬНОС

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

4.2. Мажоритарный метод определения фаз /-грамм.

4.3. Определение фаз «-грамм путем декодирования М-кодов вылавливанием ошибок.

4.4. Выигрыш от использования разработанного метода коррекции вставок/ выпадений символов.

4.5. Устройства коррекции вставок/выпадений символов.

4.6. Выводы.

5. ПОСТРОЕНИЕ УСТРОЙСТВ КОРРЕКЦИИ ОШИБОК ИНФОР

МАЦИОННЫХ КАНАЛОВ ВНЕШНИХ ЗАПОМИНАЮЩИХ

УСТРОЙСТВ ЭВМ.

5.1. Структурно-функциональная организация устройств коррекции ошибок информационных каналов ВЗУ ЭВМ.

5.2. Синтез устройств кодирования и вычисления синдромов.

5.3. Синтез устройств помехоустойчивой групповой синхронизации.

5.4. Разработка УКО контроллера подсистемы оптической памяти ОМЗУ

5.5. Разработка УКО адаптера вещательной системы распространения компьютерной информации АСРКИ.

5.6. Перспективы дальнейшего повышения эффективности коррекции ошибок в ВЗУ ЭВМ.

5.7. Выводы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Соломона с неполным вылавливанием ошибок в области проверочных символов;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Также результаты работы были использованы в фирме 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.

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

В основных работах опубликованных в соавторстве, и приведенных в библиографическом списке, лично соискателем разработаны: в [102-105,107110] - алгоритм синдромного декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния, метод поиска неизвестных невязок, параллельная организация поиска невязок, структурно-функциональная организация декодера; в [114,117,119] — методика выбора вектора ошибок из списка, управление поиском неизвестных невязок с помощью оценок надежности символов кодового слова; в [124] - методика определения корректирующих возможностей кодов Рида-Соломона; в [143,144] - алгоритмы и устройства пошагового декодирования кодов Рида-Соломона; в [150, 151,153,157-159,162,166] - метод коррекции вставок/выпадений символов путем двусторонней оценки локаторов групп символов данных, мажоритарный метод определения фаз сегментов М-последовательности; в [48,62,63,64,176] — алгоритмы установления синхронизации устройств коррекции ошибок; в [89,175,181,182] - структурно-функциональная организация декодеров и устройств коррекции ошибок.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

1. Стиффлер, Дж. Дж. Теория синхронной связи Текст. / Дж. Дж. Стиффлер. М: Связь, 1975. 488с.

2. Линдсей, В. Системы синхронизации в связи и управлении Текст./ В. Линдсей . М.: Советское радио, 1978. 600 с.

3. Системы фазовой синхронизации с элементами дискредитации Текст./ под ред. В.В. Шахильдяна. М.: Радио и связь, 1989. 320 с.

4. Лосев, В.В. Поиск и декодирование сложных дискретных сигналов Текст./ В.В.Лосев, Е.Б.Бродская, В.И.Коржик. М.: Радио и связь, 1988. 224 с.

5. Цифровые методы в космической связи Текст./ Под ред. С. Голомба. М.: Связь, 1969. 271 с.

6. Мартынов, Е.М. Синхронизация в системах передачи дискретных сообщений Текст./Е.М.Мартынов. М.: Связь, 1972. 216 с.

7. Колтунов, Н.Н. Синхронизация по циклам в цифровых системах связи Текст./Н.Н.Колтунов, В.Г.Коновалов, З.И.Лангуров. М.: Связь, 1980. 151 с.

8. Передача дискретных сообщений Текст./ под ред. В.П.Шувалова. М.: Радио и связь, 1990. 464с.

9. Bell, А.Е. Critical issues in high magnetic and optical data storage Text. / A.E. Bell // Proceedings of Soc. Photo-opt. Instrum. Eng. 1983. Vol. 382. P. 2-15.

10. Coding and signal processing for magnetic recording systems Text. / edited by Bane Vasic and Erozan M. Kurtas. CRC Press, 2005. 701 p.

11. Standard ANSI ISO/IEC 9171: Information technology -130 mm optical disk cartridges, write once, for information interchange (December 1990) Electronicresource. Mode of access: http://www.iso.org.

12. Standard ECMA-350 (ISO/IEC 17345): Data Interchange on 130 mm Rewritable and Write Once Read Many Ultra Density Optical (UDO) Disk Cartridges Capacity: 30 Gbytes per Cartridge - First Generation, 3rd editioni l

13. December 2006) Electronic recourse. Mode of access: http://www.ecma-international.org

14. Standard ECMA-183 (ISO/IEC 13481): Data Interchange on 130 mm Optical Disk Cartridges Capacity: 1 Gigabyte per Cartridge (December 1992) Electronic recourse. Mode of access: http://www.ecma-international.org

15. Standard ECMA-184 (ISO/IEC 13549): Data Interchange on 130 mm Optical Disk Cartridges Capacity: 1,3 Gigabytes per Cartridge (December 1992) Electronic recourse. Mode of access: http://www.ecma-international.org

16. Standard ECMA-189 (ISO/IEC 13614): Information Interchange on 300 mm Optical Disk Cartridges of the Write Once, Read Multiple (WORM) Type using the SSF Method (June 1993) Electronic recourse. Mode of access: http://www.ecma-international.org

17. Standard ECMA-190 (ISO/IEC 13403): Information Interchange on 300 mm Optical Disk Cartridges of the Write Once, Read Multiple (WORM) Type using the CCS Method (June 1993) Electronic recourse. Mode of access: http://www.ecma-international.org

18. Standard ECMA-195 (ISO/IEC 13842): Data Interchange on 130 mmj

19. Optical Disk Cartridges Capacity: 2 Gigabytes per Cartridge, 2 edition (June 1995) Electronic recourse. Mode of access: http://www.ecma-international.org

20. Standard ECMA-260 (ISO/IEC 15898): Data Interchange on 356 mm Optical Disk Cartridges WORM, using Phase Change Technology Capacity: 14,8and 25 Gbytes per Cartridge (June 1997) Electronic recourse. Mode of access: http://www.ecma-international.org

21. Standard ECMA-322 (ISO/IEC 22092): Data Interchange on 130 mm Magneto-Optical Disk Cartridges Capacity: 9,1 Gbytes per Cartridge (June 2001) Electronic recourse. Mode of access: http://www.ecma-international.org

22. Standard ECMA-130 (ISO/IEC 10149): Data Interchange on Read-only 120 mm Optical Data Disks (CD-ROM), 2nd edition (June 1996) Electronic recourse. Mode of access: http://www.ecma-international.org

23. Dipert, B. Upward spiral Text. / B. Dipert // EDN. 2003. August 7. P. 3848.

24. Расцвет эпохи DVD Текст. // Upgrade новый уровень ваших компьютеров. 2004. 19 нояб. (№ 4) С. 76-81.

25. HD DVD Format Overview. DVD Forum White Paper. Verl. 10 Electronic recourse. Mode of access: www.dvdforum.org/images/DVD-Forum-070605ENGrev. 110.pdf

26. Blu-ray Disc Format. White paper. Electronic recourse. Mode of access: www.blurayjukebox.com/generalbluraydiscformat-12834.pdf

27. Standard ECMA-377: Information Interchange on Holographic Versatile Disc (HVD) Recordable Cartridges Capacity: 200 Gbytes per Cartridge (May 2007) Electronic recourse. Mode of access: http://www.ecma-international.org

28. Standard ECMA-378: Information Interchange on Read-Only Memory Holographic Versatile Disc (HVD-ROM) Capacity: 100 Gbytes per disk (May 2007) Electronic recourse. Mode of access: http://www.ecma-international.org

29. Lou, D.V. Defect measurements in digital optical disk Text. / Martinez A. //Applied Optics. 1981. Vol. 20, №5. P. 887-891.

30. Типикин, А.П. Коррекция ошибок в оптических накопителях информации Текст. / А.П.Типикин, В.В.Петров, А.Г.Бабанин. Киев: Наукова думка, 1990. 169с.

31. Сивохин, Б.А. Исследование и контроль дефектности оптических дисков Текст. / Б.А.Сивохин, С.В.Тимаков, В.Г.Чубаров // Вопросы радиоэлектроники. Сер. ЭВТ: науч.-техн. сб. / М.: НИИЭИР. 1990. Вып. 13. С. 122127.

32. Felix, М.О. The optical magnetic question Text. / M.O. Felix // 5th IEEE Symp. Mass Storage Syst.: Dig. pap., Boulder, 26-28 Oct. 1982. New York, 1982. P. 43-47.

33. Characteristics of the Mass-Produced Optical Disks Text. / S. Nakamura, S. Yasui, H. Inoue, T. Nakarai // Proceedings Soc. Photo-Opt. Istrum. Eng. 1986. Vol. 695. P. 33-37.

34. Bit-error reduction in magnetic-optical disks Text. / M. Moribe, Y. Hashimoto, M. Maeda, K. Itoh, S. Ogawa. // Proceedings Soc. Photo-Opt. Istrum.

35. Eng. 1988. Vol. 899. P. 88-92.

36. High Data Transfer Rate and High Speed Accessing Optical Disk Drive Technology Text. / K. Itao, S. Hara, A. Watabe, H. Nakanishi, M. Yamamoto // Top. Meet. Opt. Data Storage, Stateline, Nev., 11-13 March 1987. Washington, D. C., 1987. P. 164-167.

37. CD-ROM Image Retrieval System Text. / T. Takeuchi, T. Saitoh, S. Komatsu, T. Nakamura // Proceedings Soc. Photo-Opt. Istrum. Eng. 1986. Vol. 695. P. 298-305.

38. M/0: Its emergence as the dominant erasable technology Text. / R.N. Gardner, T. Webster, M.A. Khan, T.A. Rinehart, A.W. Funkenbusch // Proceedings Soc. Photo-Opt. Istrum. Eng. 1986. Vol. 695. P. 48-55.

39. Takeda, T. System design of optical micro-disk subsystem Text. / T. Takeda, M. Saito, K. Itao //Proceedings Soc. Photo-Opt. Istrum. Eng. 1988. Vol. 899. P. 16-22.

40. Blom, G.M. Archival life of tellurium-based materials for optical recording Text. / G.M. Blom, D.Y. Lou // Journal of the Electrochemical Society. 1984.Vol. 131, №1. P. 146-151.

41. Okada, M. Bit error analysis for magneto-optical disks under accelerated aging conditions Text. / M. Okada, T. Habara, H. Chikugo [et al.] К. // NEC Res. And Dev. 1989, №94. P. 49-56.

42. Hartke, J.L. Defect Management Capabilities of Various DVD Technologies Electronic recourse. / J.L. Hartke. Mode of access: http://www.mscience.com/ defmgmt.pdf

43. Standard ECMA-379 (ISO/IEC DIS 10995). Test Method for the Estimation of the Archival Lifetime of Optical Media (June 2007) Electronic recourse. Mode of access: http://www.ecma-international.org

44. Михайлов, В.И. Информационные каналы запоминающих устройств на магнитных дисках Текст. / В.И. Михайлов, Г.И. Князев, Б.М. Раков М.: Энергоатомиздат, 1984. 176с.

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

46. Блох, Э.Л. Модели источника ошибок в каналах передачи цифровой информации Текст. / Э.Л.Блох, О.В.Попов, В.Я.Турин. М.: Связь, 1971. 312 с.

47. Huntoon, Z.M. On the Computation of the Probability of Post-Decoding Error Events for Block Codes Text. / Z.M. Huntoon, A.M. Michelson // IEEE Transactions on Information Theory. 1977. Vol. 23, №3. P. 399-403.

48. Барг, A.M. Оценка вероятности неправильного декодирования в канале с медленными замираниями Текст.: препр / А.М.Барг, Н.Д.Введенская, В.В.Зяблов М.: Ин-т проблем передачи информации, 1986. 50с.

49. Perera, S.R. Storage tecnologe corporation optical storage error control Text. / S.R. Perera, M. O'Keefe // Topical Meetign on Optical Data Storage: Dig. Tech. Pap., Monterey, 18-20Apr. 1984. Washington, 1984. P. WC-C2-1/WC-C2-4.

50. Bracht R. Unique features in the read/write channel of Optotech's 5984 optical disk drive Text. / R. Bracht, J. McDonald // Proceedings Soc. Photo-Opt. Istrum. Eng. 1986. Vol. 695. P. 243-246.

51. Lou, D.Y. Data Integrity in the LD1200 System Text. / D.Y. Lou // Top. Meet. Opt. Data Storage, Stateline, Nev., 11-13 March 1987. Washington, D. C., 1987. P. 174-176.

52. Takeda, T. Evaluation of sector alternation methods for optical disk Text. / T. Takeda, M. Saito // Trans. Inst. Electron. Inform, and Commun. Eng. 1988.Vol. E71, №4. P. 355-357.

53. Мак-Вильямс, Ф.Дж. Теория кодов, исправляющих ошибки Текст. / Ф.Дж. Мак-Вильямс, Н.Дж. А. Слоэн. М.: Связь, 1979. 744 с.

54. Питерсон, У. Коды исправляющие ошибки Текст. / У. Питерсон, Э.М. Уэлдон. М. Мир, 1976. 596 с.

55. Shifman, J. Error detection and correction for Sl/4 inch optical disks

56. Text. / J. Shifinan //Proceedings Soc. Photo-Opt. Istrum. Eng. 1986. Vol. 695. P. 278-293.

57. Nugent, W.R. Error Detection and Correction System for Optical Disk: Issues of Media Defect Distribution, Defect Growth, Error Management, and Disk Longevity Text. / W.R. Nugent // Proceedings Soc. Photo-Opt. Istrum. Eng. 1986. Vol. 695. P. 10-15.

58. Янсен, Й. Курс цифровой электроники Текст. /. Й.Янсен. М.: 1987. Т.З. С. 194-205.

59. Пат. 4081844 США. МКИ2 G11B 5/09, НКИ 360/48. Interleaved synch and beginning of data indicators Text. / Devore E.W., McDowell J.A. (США), заявл. 2.08.1976, №710832; опубл. 28.03.1978. 8 с.

60. А.С. 1092510 СССР, МКИ4 Н 04 L 7/08. Устройство цикловойсинхронизации для внешней памяти Текст. / Типикин А.П., Добрянский П.Е., Егоров С.И. (СССР). Заявл. 28.02.83; № 3559993/18-24; Опубл. 15.05.84, Бюл. № 18. 6с.

61. А.с. 1254457 СССР, МКИ4 G 06 F 1/04. Устройство для синхронизации внешних блоков памяти Текст. / Типикин А.П., Добрянский П.Е., Егоров С.И., Петров В.В. (СССР). Заявл. 01.02.85; № 3851468/24-24; Опубл. 30.08.86, Бюл. N 32. 6с.

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

63. Izuka, I. Block Codes Capable of Correcting both Addive and Timing Errors. Text. / I.Izuka, M.Kasahara, T.Namekawa // IEEE Transactions on Information Theory. 1980. Vol. 26 , №4. P. 393-400.

64. Долгополов, A.C. Неравномерные коды над полем G¥(q), исправляющие вставки, выпадения и замены символов Текст. / А.С.Долгополов // Кибернетика. 1986, №2. С. 93-96.

65. Пат. 0242093 ЕР, МКИ G11B20/12, G11B20/10. Resynchronization of serial data blocks Text. / Winters K.D., Spenner B.F., Bromley D.J., Baugh R.A. (США). Заявл. 03.04.87; опубл. 21.10.87. Приоритет 11.04.86, № 851049 (США). Юс.

66. Пат. 4697167 США, МКИ Н03М5/00, НКИ 340/347, 360/40. Sync pattern encoding system for data sectors written on a storage medium Text. / O'Keeffe M.J., Graba J.M., Noyes G.I. (США). Заявл. 21. 11.85, №838181; опубл. 29.09.87. 20c.

67. Пат. WO 85/00066 РСТ, МКИ G11B5/09. Synchronizing circuit Text. / Odaka К., Fukami Т., Ozaki S. (Япония). PCT/JP84/00307; заявл. 13.06.84; опубл. 03.01.85. Приоритет 14.06.83, №58-106257: (Япония). 8 с.

68. Пат. 0144813 ЕР, МКИ G11B5/09. Recording and reproducing apparatus Текст. / Murakami H. (Япония). Заявл. 12.11.84. №84113649.2; опубл. 19.06.85. Приоритет 14.11.83, №213515/83 (Япония). 31 с.

69. Блейхут, Р. Теория и практика кодов, контролирующих ошибки Текст. / Р.Блейхут. Пер. с англ. И.И. Грушко, В.М. Блиновского; под ред. К.Ш.Зигангирова. М.: Мир, 1986. 576 с.

70. Berlecamp, E.R. Bit-Serial Reed-Solomon Encoders Text. / E.R. Berlecamp // IEEE Transactions on Information Theory. 1982. Vol. 28, №6. P. 869874.

71. A.c. 1569997 СССР, МКИ5 H 03 M 13/00, 13/02. Устройство для кодирования циклических кодов Текст. / Гвоздев В.В., Типикин А.П., Егоров С.И. (СССР), заявл.23.08.88; №4477343/24-24; опубл. 07.06.1990, Бюл. №21. 6с.

72. Блох, Э.Д. Обобщенные каскадные коды (Алгебраическая теория и сложность реализации) Текст. / Э.Д.Блох, В.В.Зяблов. М.: Связь, 1976. 240 с.

73. Godlewski, P. Complexity de systemes de correction d'erreurs Text. / P. Godlewski // Traitement du signal. 1984. Vol. 1, №2. P. 179-183.

74. Savage, J.E. Complexity of Decoders: I-Classes of Decoding Rules Text. / J.E. Savage // IEEE Transactions on Information Theory. 1969. Vol. 15, №6. P. 689-695.

75. Афанасьев, В.Б. Сложность декодирования кодов Рида-Соломона

76. Текст. / В.Б.Афанасьев // IV Международный симпозиум по теории информации, доклады, часть вторая, Москва-Ленинград, 1977. С. 10-13.

77. Farrel, P.G. Code structure and decoding complexity Text. / P.G. Farrel // Impact Process. Techn. Commun.: Proc. NATO Adv. Study Inst., Chateau de Bonas, 11-12 July 1983. Dordrecht, 1985. P. 159-192.

78. Крук, E.A. Граница для сложности декодирования линейных блоковых кодов Текст. / Е.А.Крук // Проблемы передачи информации. 1989. Том 25, №3. С. 103-107.

79. Чернышева, В.А. К вопросу оценки сложности методов кодирования и декодирования Текст. / В.А.Чернышева // Методы оптимизации сложных систем. М., 1987, С. 150-154.

80. Justesen, J. On the Complexity of Decoding Reed-Solomon Codes Text. / J. Justesen // IEEE Transactions on Information Theory. 1976. Vol. 22, №2. P. 237238.

81. Афанасьев, В.Б. Быстрое декодирование БЧХ кодов Текст. / В.Б.Афанасьев // Вопросы кибернетики. Кодирование и передача информации в вычислительных сетях / С.И. Самойленко. М.: АН СССР, 1978. Вып. 42/2. С. 119-123.

82. Truong, Т.К. Fast technique for computing syndromes of BCH and ReedSolomon codes Text. / Т.К. Truong, R.L. Miller, I.S. Reed // Electronics Letters. 1979.Vol. 15, №22. P. 720-721.

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

84. Lin, S. Error Control Coding: Fundamentals and Applications Text. / S. Lin, D.J. Costello. Englewood Cliffs: Prentice-Hall, 1983. 600 p.

85. Берлекэмп, Э. Алгебраическая теория кодирования Текст. / Э.Берлекэмп. М.: Мир, 1971. 480 с.

86. Кларк, Д. Кодирование с исправлением ошибок в системах цифровойсвязи Текст. / Д.Кларк, Д.Кейн. Радио и связь, 1987. 392с.

87. Габидулин, Э.М. Кодирование в радиоэлектронике Текст. / Э.М. Габидулин, В.Б. Афанасьев. М.: Радио и связь, 1986. 176 с.

88. Berlekamp, E.R., On the Solution Alqebraic Equations over Finite Fields Text. / E.R. Berlecamp, H. Rumsey, G. Solomon // Information and Control. 1967. Vol. 10, №10. P. 553-564.

89. Chien, R.T. Hybrid methods for finding roots of a polynomial Text. / R.T. Chien, B.D. Cunninqham, I.B. Oldham // IEEE Transactions on Information Theory. 1969. Vol. 15, №2. P. 329-335.

90. Справочник по теории вероятностей и математической статистике Текст.: справочник/ B.C. Королюк, Н.И. Портенко, А.В. Скороход, А.Ф. Турбин. М.: Наука. Главная редакция физико-математической литературы, 1985. 640с.

91. Вентцель, Е.С. Теория вероятностей Текст. / Е.С.Вентцель. М.: Наука, 1969. 576 с.

92. Sudan, M. Decoding of Reed Solomon codes beyond the error-correction bound Text. / M. Sudan // Journal of Complexity, Vol.13, 1997. P. 180-193.

93. Guruswami, V. Improved Decoding of Reed-Solomon and Algebraic-Geometry Codes Text. / V. Guruswami, M. Sudan // IEEE Trans. Inform. Theory, 1999. Vol. 45, № 6. P. 1757-1767.

94. Morii, M. On error-correcting capability for Reed-Solomon codes Text. / M. Morii // IEICE Technical Report, 1990. May (IT90-0)

95. Blahut, R.E. Transform Techniques for Error Control Codes Text. / R.E. Blahut // IBM J. Res. Develop. 1979. Vol.23, №3. P. 299-315.

96. 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. 2004. Vol. 52, №12. P. 2052-2056.

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

98. Егоров, С.И. Коррекция ошибок в информационных каналах периферийных устройств ЭВМ Текст.: монография / С.И. Егоров; Курск, гос. техн. ун-т. Курск, 2008. 252 с.

99. 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.

100. Egorov, S. An Algorithm for t+l 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.

101. 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.

102. Егоров, С.И. Повышение эффективности применения кодов Рида-Соломона в телекоммуникационных системах Текст. / С.И.Егоров // Цифровая обработка сигналов и ее применение: матер. 8-ой Междунар. конф. Москва, 2006. С. 53-57.

103. Скляр, Б. Цифровая связь. Теоретические основы и практическое применение. Текст.: [пер. с англ.] / Б. Скляр. Изд. 2-е, испр. М.: Издательский дом «Вильяме», 2004. 1104с.

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

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

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

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

108. Prange, Е. The use of information sets in decoding cyclic codes Text. / E. Prange // IRE Trans. 1962. Sept. (vol. IT-8). P. 5-9.

109. Benyamin-Seeyar, A. Capability of the Error-Trapping Technique in Decoding Cyclic Codes Text. / A. Benyamin-Seeyar, S.G.S. Shiva, V.K. Bhargava // IEEE Trans. Inform. Theory, 1986. March (vol. IT-32). P. 166-180.

110. Пат. WO 89/06071 PCT, МКИ4 H03M13/0. Multiple error trapping Текст. / Tong P. (США). Заявл. 09.12.88; PCT/US88/04406; опубл. 29.06.89. 34c.

111. Massey, J.L. Step-by-step Decoding of the Bose-Chaudhuri-Hocquenghem Codes Text. / J.L. Massey // IEEE Trans. Inform. Theory, 1965. Oct. (vol. IT-11). P. 580-585.

112. Wei, S.W. High-Speed Decoder of Reed-Solomon Codes Text. / S.W. Wei, C.H. Wei // IEEE Trans. Inform. Theory, 1993. Nov. (vol. IT-41). P. 15881593.

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

114. Текст. / С.И.Егоров // Оптико-электронные приборы и устройства в системах распознавания образов, обраб. изображ. и символьной информ.: матер. 2-ой Междунар. науч.-техн конф. Курск: Курский гос. техн. ун-т, 1995. С. 74 -75.

115. Егоров, С.И. Алгоритмы пошагового декодирования РСБКР-кодов Текст. / С.И.Егоров // Методы и средства систем обработки информации: сб. науч. ст. / Курск, гос. техн. ун-т. Курск, 1997. С. 71-80.

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

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

118. Виноградов, И.М. Основы теории чисел Текст. / И.М.Виноградов. М.: Наука, 1981. 176 с.

119. Пат.WO 85/01625 РСТ, МКИ4 Н03М13/00, G06F11/10. Error correction for algebraic block codes Текст. / Berlekamp E.R., Welch L.R. (США). Заявл. 26.09.84; PCT/US84/01557; опубл. 11.04.85. 35 с.

120. Godlevski, P. Correction de deux paquets d'erreurs par un code de ReedSolomon Text. / C.T. Nguyen, S. Madkour // Ann. Telecommun. 1982. Vol. 37, №5-6. P. 258-262

121. Patel, A.M. On-the-fly decoder for multiple byte error Text. / A.M. Patel // IBM J. Res. Devolop. 1986, V. 30, №3. P. 259-269.

122. Егоров, С.И. Пошаговый декодер кодов Рида-Соломона с блокировкой ложной коррекции Текст. / С.И.Егоров, В.Е.Сошников //

123. Медико-экологические информационные технологии 2001: матер. 4-ой Междунар. науч.-техн конф. Курск: Курский гос. техн. ун-т, 2001. С. 251-253.

124. Пат. №2314639 РФ, МПК НОЗМ 13/00. Устройство декодирования кодов Рида-Соломона / Егоров С.И. (РФ). Заявл. 03.04.2006; опубл. 10.01.2008, Бюл. № 1.20с.

125. A.c. 1485415 СССР, МКИ4 Н 03 М 13/00. Устройство коррекции ошибок во внешней памяти Текст. / Типикин А.П., Гвоздев В.В., Егоров С.И. (СССР). №4240803/24-24; заявл. 07.05.87; опубл. 07.06.1989, Бюл. № 21, 28 с.

126. Егоров, С. И. Пошаговое декодирование выколотых кодов Рида-Соломона методом восстановления выколотых символов Текст. / С.И.Егоров,

127. B. Е.Сошников // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: матер. 9-й Междунар. Науч.-техн. конф. Рязань: Ряз. обл. ин-т развития образования, 2000. С. 111-114.

128. Егоров С. И. Комбинированные декодеры выколотых кодов Рида-Соломона для гибридных FEC+ARQ систем защиты от ошибок Текст. /

129. C.И.Егоров, В. Е.Сошников // Оптико-электронные приборы и устройства в системах распознавания образов, обраб. изображ. и символьной информ.:матер. Междунар. науч.-техн. конф. / Курск, гос. техн. ун-т. Курск, 2001. С. 173-175.

130. Левенштейн, В. И. О совершенных кодах в метрике выпадений и вставок Текст. / В. И.Левенштейн // Дискретная математика. 1991. Вып. 1. Т.З С.3-20.

131. Bours, P. A. Codes for Correcting Insertion and Deletion Errors Electronic recourse. / P.A. Bours // PhD thesis, Eindhoven Technical University, June 1994. Режим доступа: http://www.win.tue.nl/ math/dw/pp/wsdwpb/thesis.html

132. Davey, M. C. Reliable Communication over Channels with Insertions, Deletions and Substitutions. Text. / M.C. Davey, D.J.C. MacKay // IEEE Transactions on Information Theory. 2001. Vol. 47, № 2. P. 687—698.

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

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

135. Лидл, Р. Конечные поля Текст.: в 2 т.: [пер. с англ.] / Р.Лидл, Г.Нидеррайтер. М.: Мир, 1988. Т. 2. 822 с.

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

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

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

139. Глухарев, И.Н. Точностные характеристики методов измерения параметров ошибок синхронизации в цифровых каналах передачи и воспроизведения информации Текст. / И.Н.Глухарев, С.И.Егоров // Труды КурскГТУ. №2(15). Курск, 2005. С. 88-193.

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

141. Егоров, С.И. Помехоустойчивое определение фаз «-грамм М-после-довательности Текст. / С.И.Егоров // Известия ВУЗов. Сер. Приборостроение. 2007. Т.50, №5. N. 35-40.

142. Пат. 2224282 Россия, МПК7 О 06 Б 11/00, Н 04 В 17/00. Устройство исправления ошибок синхронизации в потоке данных Текст. / С.И.Егоров, А.М.Проценко, В.С.Титов (Россия). №2002113975/09; Заявл. 28.05.2002; Опубл. 20.02.2004, Бюл. № 5. 51 с.

143. Егоров, С.И. О программно-аппаратной реализации декодеров кода Рида-Соломона для защиты от ошибок малогабаритных оптических накопителей Текст. / С.И.Егоров // Курск, политехи, ин-т. Курск, 1990. 39 с. Деп. в ИНФОРМПРИБОР, №4898.

144. Ohr, S. Error checking and correcting 1С slashes optical disk defects Text. / S. Ohr // Electron. Design. 1985. Vol. 33, №29. P. 37-38.

145. Уоллер, Jl. Первый набор ИС, реализующий контроллер для оптического дискового накопителя Текст. / Л.Уоллер // Электроника: [пер. с англ.]. Т. 61, №9. С. 46-50.

146. А.с. 1571773 СССР, МКИ5 Н 03 М 13/00, 13/02. Устройство для вычисления синдромов кода Рида-Соломона Текст. / Гвоздев В.В., Типикин А.П., Егоров С.И. (СССР). №4475891/24-24; заявл. 23.08.88; опубл. 15.06.1990, Бюл. № 22, 6 с.

147. Айверсен, У.Р. Первая микросхема для обнаружения ошибок в данных, записанных на оптическом диске Текст. / У.Р. Айверсен //

148. Электроника пер. с англ.. 1987. Т.60, №24. С. 60-61.

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

150. Пат. 2137320 РФ, МПК6 Н 04 N 7/087, Н 04 J 3/06. Устройство приема информации из канала Текст. / Егоров С.И., Бессонов Д.П. (Россия). №98111331/09; заявл. 11.06.98; опубл. 10.09.1999, Бюл. № 25, 17 с.

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