Введение к работе
Актуальность проблемы. Современные информационные технологии, являющиеся двигателем общественного прогресса, основываются на применении электронных вычислительных машин: персональных ЭВМ, кластеров и сетей ЭВМ, суперЭВМ. Эффективность применения ЭВМ во многом определяется используемыми внешними запоминающими устройствами (ВЗУ). Хранение данных в ВЗУ ЭВМ с высокой плотностью и надежностью невозможно без использования помехоустойчивого кодирования.
Теория помехоустойчивого кодирования достаточно хорошо разработана. Большой вклад в эту область знания внесли работы как зарубежных ученых: К. Шеннона, Р. Хемминга, Р. Галлагера, Ф.Дж. Мак-Вильямс, Р. Блейхута, С. Berrou и A. Glavieux, D.J.C. МасКау, так и российских: Э.Л. Блоха, В.В. Зяблова, Э.М. Габидуллина, К.Ш. Зигангирова, Е.А. Крука, В.В. Золотарева. К настоящему времени предложены и исследованы различные классы помехоустойчивых кодов, среди которых наибольшее распространение в ВЗУ ЭВМ получили коды Рида-Соломона.
Исследования в области алгоритмов декодирования, осуществленные У. Питерсоном, Э.Р. Берлекэмпом, Дж. Месси, Р. Блейхутом, Д. Форни, Y. Sugiyama, Т.К. Truong, В.Б. Афанасьевым, позволили в основном решить задачу разработки декодеров кодов Рида-Соломона в микроэлектронном исполнении для исправления аддитивных ошибок в каналах передачи и хранения данных в 80-90-е годы 20-го века. Особенности коррекции ошибок во внешних запоминающих устройствах с использованием кодов Рида-Соломона отражены в работах A.M. Patel, N. Glover, А.П. Типикина, Б.А. Савельева и др.
Однако коррекция ошибок, возникающих в каналах записи/воспроизведения ВЗУ, в настоящее время осуществляется недостаточно эффективно как с точки зрения достижения максимальной степени повышения достоверности считываемых с носителя данных, так и с точки зрения оптимальности ее аппаратной реализации.
Недостаточно высокая степень повышения достоверности считываемых данных определяется тем, что потенциальные корректирующие способности кодов Рида-Соломона в ВЗУ ЭВМ используются не полностью: число исправляемых ошибок в кодовом слове ограничивается половиной минимального кодового расстояния, недостаточно точно локализуются ошибки синхронизации, не полностью используются возможности кодовых конструкций для исправления ошибок синхронизации.
Известные алгоритмы декодирования кодов Рида-Соломона (Guruswami-Sudan, Koetter-Vardy Parvaresh-Vardy,), позволяющие исправлять ошибки за границей половины минимального расстояния кода, пока не реализованы в устройствах коррекции ошибок ВЗУ ЭВМ из-за высокой вычислительной сложности. Известные методы исправления ошибок синхронизации с использованием специального кодирования либо не
учитывают характер ошибок в каналах воспроизведения ВЗУ (М. Davey), либо требуют внесения слишком большой избыточности (P. Bours) и также не нашли применения в устройствах коррекции ошибок ВЗУ.
Таким образом, в настоящее время существует проблемная ситуация между объективной необходимостью повышения достоверности считывания данных с носителя без уменьшения его полезной емкости и отсутствием методов, алгоритмов и устройств коррекции ошибок, решающих эту задачу с приемлемой аппаратной сложностью.
В связи с вышеизложенным актуальной является научно-техническая проблема повышения эффективности коррекции ошибок, возникающих в каналах записи/воспроизведения внешних запоминающих устройств ЭВМ.
Теоретический аспект сформулированной проблемы заключается:
в развитии математического базиса процедур эффективной коррекции аддитивных и синхронизационных ошибок:
в создании методов и алгоритмов декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния;
в создании методов и алгоритмов коррекции ошибок синхронизации, учитывающих специфику ошибок, возникающих в каналах записи/воспроизведения ВЗУ;
в разработке математического базиса синтеза устройств коррекции ошибок, обеспечивающих эффективное исправление ошибок.
Практический аспект проблемы состоит в создании устройств исправления ошибок, обеспечивающих эффективную коррекцию ошибок, возникающих в каналах записи/воспроизведения внешних запоминающих устройств ЭВМ, и имеющих допустимую для современной микроэлектроники аппаратную сложность. Применение этих устройств в ВЗУ ЭВМ позволит значительно повысить качество хранения в них данных. Ключевые компоненты устройств коррекции ошибок, например, декодеры кодов Рида-Соломона могут быть использованы для повышения эффективности коррекции ошибок в каналах систем передачи данных.
Цель работы - создание теоретических и реализационных основ построения устройств коррекции ошибок, повышающих эффективность коррекции ошибок во внешних запоминающих устройствах ЭВМ.
В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:
-
Анализ состояния проблемы коррекции ошибок, возникающих в канале записи/воспроизведения данных ВЗУ и разработка структурной модели информационного канала ВЗУ.
-
Развитие теоретических основ декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния.
-
Разработка методов и алгоритмов декодирования кодов Рида-Соломона, обеспечивающих:
- исправление ошибок за границей половины минимального кодового
расстояния;
- декодирование кодов Рида-Соломона с минимальной задержкой на основе неполного вылавливания ошибок в кодовом слове.
-
Разработка методов, алгоритмов и устройств коррекции ошибок синхронизации путем использования М-последовательности.
-
Синтез структурных и функциональных схем устройств коррекции ошибок.
Объект исследования: средства коррекции ошибок, возникающих в каналах записи/воспроизведения внешних запоминающих устройств ЭВМ.
Предмет исследования: методы, модели, алгоритмы
функционирования и структурно-функциональная организация устройств коррекции аддитивных и синхронизационных ошибок, использующих помехоустойчивые коды Рида-Соломона.
Методы исследования базируются на использовании математического аппарата высшей алгебры, комбинаторики, теории вероятностей, теории помехоустойчивого кодирования, имитационного моделирования, теории проектирования устройств ЭВМ.
Научная новизна работы:
1. Создан математический базис основных этапов процедур
эффективной коррекции аддитивных и синхронизационных ошибок,
возникающих в каналах записи/воспроизведения внешних запоминающих
устройств ЭВМ, в виде совокупности лемм, теорем и утверждений,
включающий:
теорему о взаимосвязи неизвестных невязок с вытекающими из нее следствием и утверждениями, обосновывающими возможность декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния с приемлемой аппаратной сложностью;
теорему о свойствах смежного класса с лидером веса один с вытекающими из нее следствиями, позволяющими реализовать декодирование кодов Рида-Соломона с неполным вылавливанием ошибок в области проверочных символов;
теоремы о взаимосвязи синдромов сегмента М-последовательности при его левом или правом сдвигах, позволяющие применить декодирование с вылавливанием ошибок для надежного определения фаз последовательностей сегментов.
2. Разработана система методов реализации основных этапов процедур
декодирования кодов Рида-Соломона, позволяющая повысить эффективность
коррекции ошибок, включающая:
метод поиска неизвестных невязок аналитического продолжения алгоритма Берлекэмпа-Месси на две итерации, отличающийся попарным перебором позиций ошибочных символов кодового слова;
метод определения позиций ошибочных символов в коде Рида-Соломона за границей половины минимального кодового расстояния, основанный на поиске совместимой подсистемы полиномиальных уравнений от нескольких неизвестных;
- метод пошагового исправления ошибок в кодовом слове, отличающийся
неполным вылавливанием ошибок.
3. Разработана система методов реализации совместной коррекции
аддитивных ошибок и ошибок синхронизации, позволяющая повысить
эффективность коррекции ошибок и заключающаяся в:
а) введении М-последовательности в передаваемые данные, закодированные
кодом Рида-Соломона;
б) оперативном восстановлении синхронизации данных при ее нарушении на
основе следующих разработанных методов:
методе коррекции вставок/выпадений символов путем двусторонней оценки локаторов групп символов данных;
мажоритарном методе определения фаз сегментов М-последовательности;
методе помехоустойчивого определения фаз сегментов М-последовательности путем интерпретации этих сегментов в качестве слов кода максимальной длины;
в) исправлении как первичных, так и вторичных аддитивных ошибок кодом
Рида-Соломона.
4. На основе разработанных методов создана система алгоритмов
коррекции ошибок, включающая алгоритмы:
синдромного декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния;
пошагового декодирования кодов Рида-Соломона, использующие неполное вылавливание ошибок в кодовом слове;
исправления ошибок синхронизации, использующие двусторонние оценки локаторов группы символов данных.
5. Разработан математический базис синтеза основных блоков
устройств коррекции ошибок, позволяющий снизить их сложность,
основанный на следующих теоретически обоснованных математических
процедурах и преобразованиях алгоритмов:
параллельной организации поиска невязок при исправлении дополнительных ошибок кодом Рида-Соломона, значительно сокращающей общее число вычислений обратного элемента в конечном поле;
использовании относительных фаз я?-грамм, значительно упрощающих оценку фазы сегментов М-последовательности.
6. Разработаны варианты структурно-функциональной организации
устройств коррекции ошибок, особенностью которых является введение
новых функциональных блоков, реализующих:
поиск неизвестных невязок и позиций символов ошибок в кодовом слове;
сортировку символов кодового слова по надежности;
вычисление коэффициентов виртуального многочлена остатка;
двустороннюю оценку локаторов групп символов данных.
Практическая ценность.
1. Созданные алгоритмы декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния позволяют значительно повысить эффективность применения высокоскоростных кодов
Рида-Соломона во внешних запоминающих устройствах ЭВМ без изменения существующих стандартов и без внесения дополнительной информационной избыточности при допустимой для современных СБИС аппаратной сложности.
-
На основе декодирования с неполным вылавливанием ошибок созданы пошаговые декодеры с минимальной задержкой декодирования и наименьшей аппаратной сложностью в своем классе.
-
Разработаны устройства коррекции ошибок синхронизации, позволяющие исправлять вставки или выпадения символов большой протяженности, сопровождающие пакеты аддитивных ошибок в каналах записи/воспроизведения со вставками/выпадениями символов.
-
Создано устройство коррекции ошибок для оптических накопителей информации, уменьшающее вероятность ошибок на бит в считанных данных с10"4до10"п.
Реализация результатов работы.
Исследования по тематике диссертации проводились в рамках договорных НИР КурскГТУ №1.66.00 и 1.62.00.
Результаты работы были внедрены в Институте проблем регистрации информации НАН Украины при разработке подсистемы оптической памяти и автоматизированной системы распространения компьютерной информации.
Также результаты работы были использованы в фирме Acuvision (Великобритания) при разработке аппаратуры помехоустойчивого кодирования спутниковых телекоммуникационных каналов.
Научно-методические результаты, полученные в диссертационной работе, внедрены в учебный процесс кафедры «Вычислительная техника» Курского государственного технического университета и использованы при проведении занятий по дисциплинам «Сети ЭВМ и телекоммуникации» и «Технические средства защиты и сжатия информации», в дипломном проектировании, при подготовке магистерских и двух кандидатских диссертаций.
Внедрения подтверждены соответствующими актами.
Основные положения, выносимые на защиту:
-
Математический базис основных этапов процедур эффективной коррекции аддитивных и синхронизационных ошибок.
-
Система методов реализации основных этапов процедур декодирования кодов Рида-Соломона.
-
Система методов реализации совместной коррекции аддитивных ошибок и ошибок синхронизации.
-
Алгоритмы: синдромного декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния, пошагового декодирования кодов Рида-Соломона, исправления ошибок синхронизации.
-
Математический базис синтеза основных блоков устройств коррекции ошибок
-
Структурно-функциональная организация устройств коррекции ошибок.
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 таблиц.
