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

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

ПРОЦЕНКО АЛЕКСЕЙ МИХАЙЛОВИЧ

УСТРОЙСТВО ИСПРАВЛЕНИЯ ОШИБОК СИНХРОНИЗАЦИИ В КАНАЛАХ ПЕРИФЕРИЙНЫХ УСТРОЙСТВ ЭВМ

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

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

КУРСК - 2004

Работа выполнена в Курском государственном техническом университете

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

доктор технических наук, профессор Довгаль В.М., кандидат технических наук Рубанов А.Ф.

Московский государственный институт электроники и математики (технический университет)

Защита состоится ¿4 декабря 2004 г. в часов на заседании

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

Автореферат разослан

гг ноября 2004 г.

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

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

Научный руководитель:

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

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

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

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

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

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

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

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

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

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

Известны кодовые конструкции с самосинхронизирующимися свойствами, позволяющие использовать их для исправления ошибок синхронизации. Код без запятой (CFC) и его модификации позволяют обнаруживать ошибки синхронизации, но требуют большого времени для восстановления синхронизации. Коды Левенштейна и подобные им позволяют обнаруживать и исправлять ошибки синхронизации и аддитивные ошибки, но не могут быть применены на практике из-за малого количества исправляемых ошибок и отсутствия приемлемых алгоритмов декодирования. Также известны коды, удовлетворяющие ограничениям канального кодирования (такие как SECM-коды), основным недостатком которых является неспособность исправлять ошибки синхронизации, сопровождающиеся пакетами аддитивных ошибок.

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

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

Диссертационная работы выполнена в рамках тематического плана госбюджетных НИР по Единому заказ-наряду Госкомвуза РФ Курского государственного технического университета, а также по хозяйственному договору 1.37.02 «Разработка программных средств обработки измерительной информации». Исследование поддержано грантом Минобразования РФ по фундаментальным исследованиям в области естественных и точных наук (грант Е02-2.0-81, 2003-2004 гг.).

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

В связи с этим решаются следующие задачи:

-Анализ известных методов и устройств исправления ошибок синхронизации в каналах со вставками и выпадениями символов.

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

-Разработка структурной и функциональной организации устройства исправления ошибок синхронизации (УИОС).

-Исследование достоверности исправления ошибок синхронизации устройством УИОС с помощью имитационного моделирования на ЭВМ.

Научная новизна.

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

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

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

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

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

2. Показана возможность встраивания данного устройства в структуру информационного тракта существующих систем передачи и хранения информации. На основе канальных кодов EFM и EFM+, применяемых в ВЗУ на оптических дисках, сконструированы модифицированные канальные коды

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

3. Разработана имитационная модель устройства, позволяющая оценить достоверность исправления ошибок синхронизации и ее зависимость от уровня фоновых аддитивных ошибок. В результате исследования на ЭВМ установлено, что встраивание УИОС в приемный тракт канала передачи или воспроизведения информации позволяет повысить достоверность исправления ошибок синхронизации, снизив долю неисправленных ошибок синхронизации на 1-3 порядка при вероятности ошибки синхронизации 10-3-10-5 на бит. Это позволяет снизить вероятность ошибки блока в каналах со вставками и выпадениями бит на 1-4 порядка.

Основные технические решения защищены патентом РФ № 2224282.

Реализация и внедрение. Результаты работы были использованы в ЗАО «Агентство сетевых технологий» (г. Москва), компании Асиушоп (Великобритания), внедрены в учебном процессе Курского государственного технического университета.

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

Апробация работы. Основные положения диссертационной работы докладывались и получили положительную оценку на Международных и Российских конференциях: МНТК «Распознавание-99», «Распознавание-2001», «Распознавание-2003» (г. Курск, 1999, 2001, 2003 гг.); МНТК «Медико-экологические информационные технологии» (г. Курск, 2000 г.); РНТК «Интеллектуальные и информационные системы» (г. Тула, 2000 г.); РНТК «Новые информационные технологии» (Крым, 2001, 2002 гг.); МНТК «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» (г. Рязань, 2001 г.); на научно-технических семинарах кафедры «Вычислительная техника» Курского государственного технического университета с 1999 по 2004 гг.

Публикации. Результаты диссертационной работы отражены в 11 работах, в том числе в 2 статьях, 1 патенте на изобретение, а также 8 тезисах и материалах докладов. В работах, опубликованных в соавторстве, лично автором разработаны: в [1,4,5] - мажоритарный метод нахождения величины компенсационного сдвига, в [3] - канальные коды МЕБМ и МЕБМ+, в [8, 9] -структурная организация блока вычисления величины компенсационного сдвига.

На защиту выносятся следующие положения:

1. Мажоритарный метод нахождения величины компенсационного сдвига при двусторонней оценке локатора синхрослова.

2. Функциональная организация блока вычисления величины компенсационного сдвига.

3. Алгоритм параллельного поиска существенного локатора.

4. Результаты исследования на имитационной модели УИОС характеристик достоверности исправления ошибок синхронизации.

Объем и структура работы. Работа включает введение, четыре главы, заключение, список литературы из 82 наименований и 5 приложений. Объем диссертации 117 страниц, включая 37 рисунков и 5 таблиц.

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

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

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

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

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

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

для определения

фазы

применение мажоритарных механизмов синхропоследовательности.

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

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

Достоверность исправления ошибки синхронизации может быть повышена, если перед декодированием помехоустойчивого кода с целью уменьшения числа ошибок в его кодовом слове выполнить компенсационный сдвиг информационной последовательности на количество тактов, точно равное длине вставки / выпадения. Эта задача может быть решена, если в состав функциональных узлов приемного / воспроизводящего тракта ввести дополнительное устройство исправления ошибок синхронизации (УИОС). включаемое между выделителем и декодером канального кода и работающее в режиме реального времени на тактовой частоте, выделяемой блоком фазовой автоподстройки частоты (ФАПЧ) непосредственно из принятой информационной последовательности, закодированной канальным кодом (рис. 1).

Выделенный сигнал тактовой синхронизации

Рис. 1. Схема встраивания УИОС в приемную часть канала

Основные функции устройства УИОС:

1) обнаружение вставок / выпадений;

2) вычисление длины вставки / выпадения и ее локатора в блоке данных;

3) выполнение перед декодированием канального кода компенсационного сдвига отрезка информационной последовательности, следующего за

найденной точкой срыва синхронизации, на число тактов, равное длине вставки (выпадения).

В качестве избыточной синхроинформации, используемой устройством УИОС, применяется односимвольный синхросигнал, обладающий циклическими рекуррентными свойствами. В данной работе в качестве такого синхросигнала используется m-последовательность, причем биты m-последовательности (синхробиты) вставляются в «поток данных через равные промежутки длины р, образуя р -разрядные синхрослова. Достоинством такого типа синхросигнала является то, что локатор синхрослова данных определяется не только значением связанного с ним синхробита, но и значениями соседних т-1 синхробитов, где т - степень порождающего многочлена m-последовательности. Это позволяет достичь более высокой точности локализации ошибок синхронизации по сравнению с другими типами применяемых на практике синхросигналов по причине существенно меньшей длины цикла при той же информационной избыточности.

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

ограничений, т.е. ограничений на минимальную и максимальную длину последовательности нулевых символов. В данной работе сконструированы модифицированные канальные коды MEFM и MEFM+ (применяемые в ВЗУ стандартов CD и DVD соответственно), слова которых содержат синхробиты m-последовательности.

Код MEFM построен на основе кода EFM путем модификации связывающей последовательности и увеличения ее длины с 3 до 6 бит при сохранении таблицы кодовых слов. Длякода EFM 8-битовое информационное слово кодируется в 17-битовую последовательность, для MEFM - в 20-битовую, т.е. дополнительная избыточность составила 3/20=0,15. Для кода MEFM+, сконструированного на основе EFM+, построена таблица кодовых слов, содержащих на фиксированных позициях биты синхропоследовательности. Длина кодового слова увеличена с 16 до 20 бит, дополнительная избыточность составила 4/20 = 0,2.

Для исправления ошибок синхронизации в работе использован и развит предложенный СИ. Егоровым метод исправления ошибок синхронизации на основе двусторонней оценки локатора синхрослова. Под локатором понимается порядковый номер синхробита (и связанного с ним синхрослова) внутри периода синхропоследовательности. Особенность метода заключается в том, что оценка локатора каждого синхробита осуществляется дважды, с использованием (j'-l) синхробитов слева и справа от оцениваемого бита Выбор одной из двух оценок осуществляется по наибольшему весу. Эта особенность позволяет значительно снизить негативное влияние группирующихся аддитивных ошибок на точность локализации ошибки синхронизации. Данный метод предусматривает использование левых и

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

Для обеспечения точного нахождения позиции и величины требуемого компенсационного сдвига создан мажоритарный метод нахождения величины компенсационного сдвига. Задача формулируется следующим образом. Каждый бит потока {/"/}, принимаемого из канала, считается связанным с некоторым словом С,, сформированным по принципу С1 = (г(,г,.,,.Определенные

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

значение которого соответствует утверждению, что бит является синхробитом и первым битом синхрослова . Далее, для каждого синхробита такого, что , необходимо найти порядковый номер (локатор) этого

синхробита А,. Первая задача является задачей определения границ синхрослов (фазы синхропоследовательности в потоке данных), вторая - порядковых номеров синхрослов (фазы символов в синхропоследовательности). Значения IV, и Л, являются стробом и адресом записи в буферную память соответственно, и однозначно описывают величину компенсационного сдвига. Математическая модель метода выглядит следующим образом.

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

где г, = (ц,Гц_в+[) - вектор битов, принятых из канала на последних а тактах. При , этом формирование символов производится как из битов синхропоследовательности, так и из информационных битов по тому же принципу. Для каждого символа синхропоследовательности табличным способом определяется его локатор, т.е. порядковый номер . Левые и правые окна содержат относительные локаторы символов синхропоследовательности, т.е. локаторы, сформированные по принципу

где к = \,р - номер окна,' / = 0,7-1, ) =у-\+(т-2), 2(у-1),' у - размер окна, - период т-последовательности. Для каждого окна

определяется локатор с наибольшим весом (числом вхождений в окне) и собственно его вес

____

(4)

1(5)

" упорядоченный

набор множеств, такой, что =х(тос1 Т). Далее, для всех

к = 1,р, д = 1,2, отыскивается

У,*

Тогда значения фазы границы синхрослова и локатора синхрослова находится из следующих вьфажений

N1 = а^тах/г*(7с),

Номер синхрослова и признак его границы формируются как Л, =(£,+(*/р))тос17\ (6)

Г1, Л', = ((то<1 р)

(О, Л', Ф /(тос! р) (7)

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

На рис. 2 приведена функциональная организация блока вычисления величины компенсационного сдвига, основанная на описанном выше методе и позволяющая выполнить его экономичную аппаратную реализацию. На каждом такте на вход блока поступает бит потока данных, принятый из канала, и производится вычисление выходных значений Щ и А, . Формирователь синхросимволов реализует операцию (1) выделения символа синхропоследовательности. Формирователь локаторов осуществляет преобразование символа синхропоследовательности в его локатор и может быть реализован табличным способом. Блок нахождения существенного локатора выполняет вычисление значений и , которые, в свою очередь, используются для формирования адреса и строба записи по формулам (6) и (7) в соответствующих функциональных блоках.

Рис. 2. Функциональная организация блока вычисления величины компенсационного сдвига

При использовании предлагаемого метода мажоритарного вьиисления компенсационного сдвига сложной задачей является нахождение существенного локатора символа, т.е. значения элемента окна с наибольшим весом по формулам (4) и (5), реализуемое блоком нахождения существенного локатора на рис. 2. Задача ставится следующим образом. Имеется очередь, элементами которой являются целые числа, описывающие локаторы символов синхропоследовательности. В очередь на каждом шаге помещается один элемент и удаляется другой элемент 82. Необходимо на каждом шаге получить значение элемента, встречающегося в очереди наибольшее число раз, и количество его вхождений в очередь.

Таблица 1

Алгоритм параллельного поиска существенного локатора символа синхропоследовательности

Шаг П1 П2 ПЗ П4

1 МЗИ1-»х М4[0]->Ь

2 Ш^Нх'

3 М1[Ц-»Р х'+1->М2[ч1 х'-»МЗ[з11 М4[Х'1-»5>

4 81->М4[Х']

5 х->МЗ[У] 5'->М4[Х1

6 МЗ^-^х

7 М2[Ч-11->х'

8 х'-1->М2[Ч-1] х'-1->МЗ[$2] М4[Х'-1]->8'

9 з2->М4[Х'-11

10 х-ЭМЗИП в'->М4[х1

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

шагам. Новизна данного алгоритма заключается в использовании параллельного принципа, позволившего сократить количество тактов в одном цикле работы. Для этого используются 4 независимых блока памяти М1-М4. Алгоритм приводится в таблице 1. Входные данные: - элемент, добавленный в очередь на данном цикле; $2 - элемент, удаленный из очереди на данном цикле. Выходные данные: Ь - элемент, имеющий наибольшую частоту; Р количество вхождений элемента Ь в очереди, П1-П4 - параллельные потоки.

В третьей главе описывается разработка структурной и функциональной организации УИОС, реализованного на основе мажоритарного метода нахождения величины компенсационного сдвига. Приводятся структурная схема УИОС (рис. 3), функциональные схемы его отдельных блоков, временные диаграммы управляющих сигналов.

Рис. 3. Структурная схема УИОС

Блок 1 формирования символов синхропоследовательности предназначен для выделения го-разрядных символов из принятой последовательности данных. Блок формирования локаторов реализует табличное преобразование символов синхропоследовательности в их локаторы. С помощью вычитателя 5 осуществляется вычисление относительного локатора по формулам (2) и (3). Блок нахождения существенного локатора реализует алгоритм параллельного поиска существенного локатора символа синхропоследовательности и выдает значения Ц и Ы,, которые используются для вычисления адреса записи А, и генерации строба записи ¡V,. Формирование адреса А, осуществляется с помощью сумматора 7 и блока разрешения записи 12, реализующего алгоритм разрешения записи в буферное ОЗУ. Строб Ж, формируется по условию

равенства выходного значения блока нахождения фазы синхросимвола значению счетчика 11 по модулю

Верхняя оценка аппаратной сложности устройства при реализации на ПЛИС семейства ХШпх "Уйех-Н составила в слайсах

Требуемый объем встроенной памяти кристалла равен

битов, где - степень

порождающего многочлена синхропоследовательности, р - разрядность синхрослова, у ~ размер окна При реализации УИОС с параметрами т= 7, оценка сложности составила 240 слайсов и 48 Кбит встроенной памяти кристалла, что позволяет использовать ПЛИС ХШпх "Уйех-П ХС2У80. Временная сложность выполнения обработки одного входящего бита составляет 10 тактов, что позволяет при реализации на современных ПЛИС с тактовой частотой 200 МГц обеспечить работу при скорости передачи данных до 20 Мбит/с. При реализации на БМК с тактовой частотой 2 ГГц скорость передачи может быть увеличена до 200 Мбит/с.

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

В качестве основы для построения модели источника ошибок выбрана модель Беннета-Фройлиха, которая задается небольшим числом параметров и не накладывает жестких ограничений на вид закона распределения пакетов ошибок. Каждый пакет ошибок описывается двумя целыми числами и обозначающими соответственно длину безошибочного интервала и длину следующего за ним пакета аддитивных ошибок. Добавлен третий параметр пакета ошибок описывающий длину ошибки синхронизации, значение которого распределено по нормальному закону. Среднеквадратичное отклонение а выбрано пропорциональным длине пакета аддитивных ошибок Ь4. (Т~с3Ь. Модель источника ошибок описывается тремя параметрами: вероятностью возникновения пакета ошибок , параметром геометрического распределения длин пакетов аддитивных ошибок и коэффициентом длины ошибки синхронизации

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

диапазона параметров источника ошибок (вероятности ошибки синхронизации

на бит ?„ = 10"3...Ю"5

Ю^.ЛО"3)

вероятности аддитивной ошибки на бит Ра эти значения составили: т = 1, у - 20 - 24, Я = 2,4,8.

С использованием полученных значений параметров было выполнено имитационное моделирование системы передачи или хранения информации с целью получения характеристик достоверности исправления ошибок синхронизации с помощью УИОС. В качестве величины, характеризующей названную достоверность, выбрана доля неисправленных ошибок синхронизации Q, т.е. отношение числа блоков, поврежденных ошибками синхронизации и не исправленных помехоустойчивым кодом, к общему числу переданных блоков, поврежденных ошибками синхронизации (исправленных и неисправленных). Блок данных представляет собой последовательность перемеженных символов из Я- 2 слов кода Рида-Соломона (255, 239) над 28) с /=8. Испытания проводились для следующих параметров модели источника ошибок:

На рис. 4 приведены графики для Q при различных вероятностях ошибки синхронизации Рг и аддитивной ошибки Р, пересчитанных на бит. В целях сравнения величины Q выполнялось моделирование системы без использования УИОС и с использованием УИОС. В первом случае доля неисправленных ошибок синхронизации составила 0,99-1,0, поэтому кривые для этого случая находятся практически на оси абсцисс. Кривые, соответствующие системе с УИОС, описывают степень повышения достоверности исправления ошибок синхронизации в результате встраивания разработанного устройства УИОС в приемные тракты каналов ПУ ЭВМ. Для диапазона Рг — 10~3...Ю~5 степень повышения достоверности Q составила 1-3 порядка.

Рис. 4. Доля неисправленных ошибок синхронизации

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

преимущество системы с УИОС по величине Рь на 1-4 порядка. При дальнейшем уменьшении вероятности ошибки синхронизации наблюдается схождение кривых соответствующих системам с применением и без применения УИОС вследствие уменьшения числа неисправленных блоков для

последнего случая.

^

1,006-05 1.00Е-04 1.00Е-03 1,ООЕ-()2 1.00Е-01 1,ООЕЮО

1.00Е-02 1,ООе-Ш 1.К1Е-М 1,«1Е-С6 1,ООЕ-М Р,

„ . без УИОС -Л-7,МЕЛЗ -»-3,88Е-03 -а-7,(9Е-04 *' С УИОС -в-7,в«Е-03 -»-З.ЮЕ-ОЗ -*-7,№Е-04

Рис. 5. Вероятность неисправимой ошибки блока

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

В приложениях приводятся таблица кодовых слов канального кода MEFM+, функциональные схемы блоков УИОС, листинг программной модели источника ошибок, листинги программных модулей программы имитационного моделирования УИОС, акты об использовании результатов диссертации.

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

1. Обоснована необходимость встраивания УИОС в приемный тракт канала ПУ ЭВМ в целях повышения достоверности исправления ошибок синхронизации и, в конечном итоге, достоверности приема (воспроизведения) данных. Показана практическая возможность использования т-последовательности в качестве односимвольного синхросигнала в каналах

ПУ ЭВМ на примере каналов хранения информации на оптических дисках. С этой целью созданы модификации канальных кодов MEFM и MEFM+, содержащие односимвольный синхросигнал и характеризующиеся дополнительной избыточностью 0,15 и 0,2 соответственно.

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

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

4. Разработана структурная и функциональные схемы УИОС. Выполнена оценка аппаратной сложности и быстродействия устройства. Оценка сложности устройства составила 240 слайсов ПЛИС семейства Xilinx Virtex-П и 48 Кбит встроенной памяти кристалла. Временная сложность выполнения обработки одного входящего бита составляет 10 тактов, что позволяет при реализации на современных ПЛИС обеспечить работу при скорости передачи данных до 20 Мбит/с.

5. В результате имитационного моделирования на ЭВМ выбраны параметры УИОС и получены численные характеристики достоверности исправления ошибок синхронизации устройством. Встраивание УИОС в канал передачи или воспроизведения информации позволяет повысить достоверность исправления ошибок синхронизации, снизив долю неисправленных ошибок синхронизации на 1-3 порядка при вероятности ошибки синхронизации 10~3-10-5 на бит. Это позволяет снизить вероятность ошибки блока на 1-4 порядка.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

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

2. Проценко A.M. Коды для защиты от ошибок синхронизации // Методы и средства систем обработки информации: Сб. науч. статей. Вып. 3. Курск, 2003. С. 118-123.

3. Проценко A.M., Типикин А.П. Исправление ошибок синхронизации в каналах с (d, к)-ограничениями // Методы и системы обработки информации: Сб. науч. статей в 2-х частях. Часть 2 / Под ред. С.С. Садыкова, Д.Е. Андрианова. М.: Горячая линия - Телеком, 2004. С. 110-117

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

5. Егоров СИ., Проценко А.М. Процедура исправления ошибок типа вставок/выпадений бит в каналах передачи цифровой информации // Медико-экологические информационные технологии: Материалы третьей междунар. науч.-техн. конф. Курск, 2000. С. 136-139.

6. Проценко А.М. Метод исправления ошибок типа вставок/выпадений бит в каналах передачи цифровой информации // Интеллектуальные и информационные системы: Тезисы докладов региональной науч.-техн. конф. Тула: ТулГУ, 2000. С. 45-47.

7. Проценко А. М. Метод восстановления синхронизации в каналах передачи данных // Новые информационные технологии: Тезисы докладов девятой междунар. студенческой школы-семинара. М: МГИЭМ, 2001. С. 63-65.

8. Егоров С.И., Проценко А.М. Устройство защиты от ошибок синхронизации в каналах передачи данных // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: Материалы пятой междунар. науч.-техн. конф. -Курск, 2001. С. 168-170.

9. Егоров С.И., Проценко А. М. Защита от ошибок синхронизации в системах передачи и хранения информации // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: Сборник материалов 10 междунар. науч.-техн. конф. Рязань, 2001. С. 89-91.

10. Проценко А.М. Метод защиты от ошибок в каналах со вставками и выпадениями символов // Новые информационные технологии: Тезисы докладов 10 юбилейной междунар. студенческой школы-семинара. М.: МГИЭМ, 2002. С. 87-89.

11. Проценко AM. Программная модель системы защиты от ошибок в каналах со вставками и выпадениями бит // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: Материалы шестой междунар. науч.-техн. конф. Курск, 2003. С. 170-172.

Соискатель А. М. Проценко

ВД №06430 от 10.12.01 Подписано в печать 22 .ИМ Формат 60x84 1 /16. Печать офсетная. Печ. л. 1,0. Тираж 100 экз. Заказ 29/ Курский государственный технический университет. Издательско-полиграфический центр Курского государственного технического университета. 305040, Курск, ул. 50 лет Октября, 94

»24573

Введение.

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

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

1.2 Классификация методов исправления вставок и выпадений бит

1.3 Анализ методов и устройств синхронизации в каналах со вставками и выпадениями бит

1.3.1 Методы и устройства, основанные на самосинхронизирующихся свойствах помехоустойчивых кодов

1.3.2 Методы и устройства, основанные на вставке синхроинформации в поток данных

1.4 Выводы

2 Разработка метода и алгоритмов исправления ошибок синхронизации в каналах периферийных устройств ЭВМ

2.1 Постановка задачи повышения достоверности исправления ошибок синхронизации

2.2 Описание структуры синхросигнала, применяемого для исправления ошибок синхронизации

2.2.1 Свойства m-последовательностей, позволяющие использовать их в качестве односимвольного синхросигнала

2.2.2 Использование односимвольного синхросигнала в каналах с (с1,к)-ограничениями

2.3 Метод исправления ошибок синхронизации с использованием двусторонней оценки локатора синхрослова

2.4 Мажоритарный метод нахождения величины компенсационного сдвига

2.5 Функциональная организация блока вычисления компенсационного сдвига

2.6 Алгоритм параллельного поиска существенного локатора символа синхропоследовательности

2.7 Выводы

3 Разработка устройства исправления ошибок синхронизации в каналах периферийных устройств ЭВМ

3.1 Структурная и функциональная организация устройства исправления ошибок синхронизации

3.2 Блок нахождения существенного локатора

3.3 Блок разрешения записи в буферное ОЗУ

3.4 Оценка сложности и быстродействия устройства исправления ошибок синхронизации -

3.5 Выводы

4 Исследование достоверности исправления ошибок синхронизации с помощью имитационного моделирования

4.1 Описание модели источника ошибок

4.2 Принципы имитационного моделирования УИОС и организация программной модели

4.3 Оценка значений параметров УИОС, обеспечивающих наибольшую достоверность исправления ошибок синхронизации

4.4 Анализ характеристик достоверности исправления ошибок синхронизации с помощью УИОС

4.5 Выводы. 108 Заключение 110 Список литературы 112 Приложение I. Таблица кодовых слов кода MEFM+" " 121 Приложение II. Функциональная схема блока нахождения существенного локатора 128 Приложение III. Листинг программной модели источника ошибок 131 Приложение IV. Листинги программных модулей программы имитационного моделирования УИОС 133 Приложение V. Акты об использовании результатов диссертации

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

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

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

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

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

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

Известны кодовые конструкции с самосинхронизирующимися свойствами, позволяющие использовать их для исправления ошибок синхронизации. Код без запятой (CFC) и его модификации позволяют обнаруживать ошибки синхронизации, но требуют большого времени для восстановления синхронизации. Коды Левенштейна и подобные им позволяют обнаруживать и исправлять ошибки синхронизации и аддитивные ошибки, но не могут быть применены на практике из-за малого количества исправляемых ошибок и отсутствия приемлемых алгоритмов декодирования. Также известны коды, удовлетворяющие ограничениям канального кодирования (такие как SECM-коды), основным недостатком которых является неспособность исправлять ошибки синхронизации, сопровождающиеся пакетами аддитивных ошибок.

Известны разнообразные методы исправления ошибок синхронизации, основанные на внесении в передаваемую информационную последовательность специального регулярного синхросигнала в целях обеспечения возможности восстановления синхронизации. Общими недостатками этих методов, в зависимости от типа используемого синхросигнала, являются или большое время восстановления синхронизации, или низкая точность локализации ошибок синхронизации. Недостатком методов, использующих синхроинформацию в виде односимвольного синхросигнала, является низкая точность локализации ошибок синхронизации, если они сопровождаются пакетами аддитивных ошибок. Это приводит к возникновению протяженных пакетов остаточных аддитивных ошибок на выходе декодера канального кода, и, следовательно, к снижению достоверности исправления ошибок. 6

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

Диссертационная работы выполнена в рамках тематического плана госбюджетных НИР по Единому заказ-наряду Госкомвуза РФ Курского государственного технического университета, а также по хозяйственному договору 1.37.02 «Разработка программных средств обработки измерительной информации». Исследование поддержано грантом Минобразования РФ по фундаментальным исследованиям в области естественных и точных наук (грант Е02-2.0-81, 2003-2004 гг.).

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

В связи с этим решаются следующие задачи:

-Анализ известных методов и устройств исправления ошибок синхронизации в каналах со вставками и выпадениями символов.

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

-Разработка структурной и функциональной организации устройства исправления ошибок синхронизации (УИОС).

-Исследование достоверности исправления ошибок синхронизации устройством УИОС с помощью имитационного моделирования на ЭВМ.

Научная новизна.

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

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

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

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

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

2. Показана возможность встраивания данного устройства в структуру информационного тракта существующих систем передачи и хранения информации. На основе канальных кодов EFM и EFM+, применяемых в ВЗУ на оптических дисках, сконструированы модифицированные канальные коды MEFM и MEFM+, содержащие односимвольный синхросигнал для целей исправления ошибок синхронизации и удовлетворяющие ограничениям существующих канальных кодов. Сконструированные коды могут быть применены в современных ВЗУ на оптических дисках с целью защиты от ошибок синхронизации.

3. Разработана и исследована на ЭВМ имитационная модель устройства, позволяющая оценить достоверность исправления ошибок синхронизации и ее зависимость от уровня фоновых аддитивных ошибок. В соответствии с полученными результатами установлено, что встраивание УИОС в приемный тракт канала передачи или воспроизведения информации позволяет повысить достоверность исправления ошибок синхронизации, снизив долю неисправленных ошибок синхронизации на 1-3 порядка при 8 вероятности ошибки синхронизации 10~3-10~5 на бит. Это позволяет снизить вероятность ошибки блока в каналах со вставками и выпадениями бит на 1—4 порядка.

Основные технические решения защищены патентом РФ № 2224282.

Реализация и внедрение. Результаты работы были использованы в ЗАО «Агентство сетевых технологий» (г. Москва), компании Acuvision (Великобритания), внедрены в учебном процессе Курского государственного технического университета.

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

Апробация работы. Основные положения диссертационной работы докладывались и получили положительную оценку на Международных и Российских конференциях: МНТК «Распознавание-99», «Распознавание-2001», «Распознавание-2003» (г.Курск, 1999, 2001, 2003 гг.); МНТК «Медико-экологические информационные технологии» (г.Курск, 2000 г.); РНТК «Интеллектуальные и информационные системы» (г.Тула, 2000 г.); РНТК «Новые информационные технологии» (Крым, 2001, 2002 гг.); МНТК «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» (г.Рязань, 2001 г.); на научно-технических семинарах кафедры «Вычислительная техника» Курского государственного технического университета с 1999 по 2004 гг.

На защиту выносятся следующие положения:

1. Мажоритарный метод нахождения величины компенсационного сдвига при двусторонней оценке локатора синхрослова.

2. Функциональная организация блока вычисления величины компенсационного сдвига.

3. Алгоритм параллельного поиска существенного локатора.

4. Результаты исследования на имитационной модели УИОС характеристик достоверности исправления ошибок синхронизации

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

4.5 Выводы.

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

2. Создана процедура моделирования системы передачи или хранения информации с использованием УИОС.

3. На программной модели получены оптимальные значения параметров УИОС (степени порождающего полинома т-последовательности т, размера окна у, глубины перемежения кодовых слов помехоустойчивого кода Я) для различных наборов параметров источника ошибок.

4. На программной модели получены характеристики достоверности исправления ошибок синхронизации и достоверности передачи (воспроизведения) данных. Определен рабочий диапазон вероятностей ошибки синхронизации для УИОС - каналы с вероятностью ошибки синхронизации на бит, равной 10~3-10~7. В этом диапазоне встраивание УИОС в канал передачи или воспроизведения информации позволяет повысить достоверность исправления ошибок синхронизации, снизив долю неисправленных ошибок синхронизации на 1—3 порядка при вероятности ошибки синхронизации 10~3-1(Г5 на бит. Это позволяет снизить вероятность ошибки блока на 1 -4 порядка.

Заключение

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

1. Обоснована необходимость встраивания УИОС в приемный тракт канала ПУ ЭВМ в целях повышения достоверности исправления ошибок синхронизации и, в конечном итоге, достоверности приема (воспроизведения) данных. Показана практическая возможность использования ш-последовательности в качестве односимвольного синхросигнала в каналах ПУ ЭВМ на примере каналов хранения информации на оптических дисках. С этой целью созданы модификации канальных кодов MEFM и MEFM+, содержащие односимвольный синхросигнал и характеризующиеся дополнительной избыточностью 0,15 и 0,2 соответственно.

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

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

4. Разработана структурная и функциональные схемы УИОС. Выполнена оценка аппаратной сложности и быстродействия устройства.

Оценка сложности устройства составила 240 слайсов ПЛИС семейства Xilinx Virtex-II и 48 Кбит встроенной памяти кристалла. Временная сложность выполнения обработки одного входящего бита составляет 10 тактов, что позволяет при реализации на современных ПЛИС обеспечить работу при скорости передачи данных до 20 Мбит/с.

5. В результате имитационного моделирования на ЭВМ выбраны параметры УИОС и получены численные характеристики достоверности исправления ошибок синхронизации устройством. Встраивание УИОС в канал передачи или воспроизведения информации позволяет повысить достоверность исправления ошибок синхронизации, снизив долю неисправленных ошибок синхронизации на 1-3 порядка при вероятности ошибки синхронизации 10~3-10-5 на бит. Это позволяет снизить вероятность ошибки блока на 1-4 порядка.

1. Егоров С.И. Аппаратные средства и алгоритмы защиты от ошибок внешней памяти и телевизионного канала ПЭВМ. // Диссертация на соискание ученой степени кандидата технических наук. Курск: 1995.

2. Передача дискретных сообщений: Учебник для вузов / В. П. Шувалов, Н. В. Захарченко, В. О. Шварцман и др.; Под ред. В. П. Шувалова. М.: Радио и связь, - 1990 - 464 е.

3. Бертсекас Д., Галлагер Р. Сети передачи данных: Пер. с англ. -М.: Мир, 1989.-544 е.

4. Элементы теории передачи дискретной информации. Под редакцией Пуртова Л.П. М.: Связь, 1972. 232 с.

5. Пуртов Л.П., Замрий А.С., Захаров А.И., Охорзин В.М. Элементы теории передачи дискретной информации. М.: Связь, 1972. - 232 с.

6. Стиффлер Дж. Дж. Теория синхронной связи. М: Связь, 1975.488с.

7. Проценко A.M. Коды для защиты от ошибок синхронизации // Методы и средства систем обработки информации: Сб. науч. статей. Вып. 3. Курск, 2003. С. 118-123.

8. P.A.H.Bours. Codes for Correcting Insertion and Deletion Errors // PhD thesis, Eindhoven Technical University, June 1994. http://www.win.tue.nl/math/dw/pp/wsdwpb/thesis.html

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

10. S.W. Golomb, В. Gordon and L.R. Welsh. Comma-Free Codes // Canadian Journal of Mathematics, vol. 10, no. 2, 1958. PP. 202-209

11. Ely S.R. et al. High-speed decoding techniques for slip detection in data transmission systems using modified cyclic block codes // Electronic Letters, Vol. 19, No. 3, 1989. PP. 127-138

12. А.С. 1243148 (СССР). Устройство циклового фазирования приемника дискретной информации / А.П.Чурус, В.И. Величко, В.И. Федорченко.

13. Слепаков В.Б., Блиева В.В. Цикловая синхронизация в системах передачи информации циклическими кодами // Электросвязь, № 6, 1989. С. 140-154.

14. E.N. Gilbert. Synchronization of Binary Messages. // IRE Transactions on Information Theory, Vol. 6, No. 4, September 1960. PP. 470-477.

15. T.R. Hatcher. On a Family of Error-correcting and Synchronizable Codes // IEEE Transactions on Information Theory, vol. 15, no. 5, September 1969. Pp. 620-624.

16. J.J. Stiffler. Comma-free Error-correcting Codes // IEEE Transactions on Information Theory, Vol. 11, no. 1, January 1965. PP. 107-111.

17. S.E. Tavares and M. Fukada. Matrix Approach to Synchronization Recovery for Binary Cyclic Codes // IEEE Transactions on Information Theory. Vol. 15, no. 1, January 1969. PP. 93-101.

18. Левенштейн В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов // Докл. АН СССР, 163, №4, 1965. С. 845-848.

19. Левенштейн В.И. Асимптотически оптимальный двоичный код с коррекцией выпадения одного или двух смежных бит // Проблемы кибернетики, т. 19, 1967. С. 298-304

20. Тененгольц Г.М. Класс кодов, исправляющих выпадение бита и ошибку в предыдущем бите // Автоматика и телемеханика, т. 37, вып. 5, 1976. С. 174-179

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

22. Н.М. Hilden, D.G. Howe, E.J.Weldon jr. Shift Error Correcting Modulation Codes // IEEE Transactions on Magnetics, Vol. MAG-27, no. 6, November 1991. PP. 4600-4605

23. P.Lee, J.K.Wolf. Combined error correction/Modulation codes // IEEE Transactions on Magnetics, vol. MAG-23, no.5, September 1987. PP. 3861-3683.

24. P.Lee, J.K.Wolf. A general error-correctiong code construction for run-length limited binary channels // IEEE Transactions on Information Theory, vol. IT-35, no.6, November 1989. PP. 1330-1335.

25. Y.Lin, J.K.Wolf. Combined ECC/RLL codes // IEEE Transactions on Magnetics, vol. MAG-24, no. 6, November 1988, PP. 2527-2529.

26. A.V.Kuznetsov, A.J.Vinck. Single Peak-Shift Correction in (d,k)-sequences // Proceedings of the 1991 International Symposium on Information Theory. Budapest, Hungary, June 1991. P. 256.

27. A.V.Kuznetsov, A.J.Vinck. A coding scheme for single peak-shift correction in (d,k)-constrained channels // IEEE Transactions on Information Theory, vol. IT-39, no. 4, July 1993. PP. 1444-1450.

28. E. Tanaka, T. Kasai. Synchronization and substitution error-correction codes for the Levenshtein metric // IEEE Transactions on Information Theory, vol. IT-22, no. 2, March 1976. PP. 156-162.

29. R.M.Roth, P.H.Siegel. Lee-metric BCH Codes and their Application to Constrained and Partial-Response Channels // IEEE Transactions on Informatoin Theory, vol.40, no.4, July 1994. PP. 1083-1096.

30. F.F. Sellers., Jr. Bit loss and gain correction code // IRE Transactions on Information Theory, Vol.8, no.l, January 1962. PP. 35-38.

31. Способ цикловой синхронизации / Хонма Конти; Мацусита дэнки санге к.к. Заявка 59-171234 , Япония. Заявл. 17.03.83 № 58-44901, опубл.2709.84, МКИ Н 04 L 7/08.

32. Система с переменным цикловым синхросигналом / Като Тосиро; Фуд-зицу к.к. Заявка 60-236535, Япония. Заявл. 10.05.84., №59-93008, опубл.2511.85, МКИ Н 04 L 7/08

33. U.S. Patent 4607378. Detector for detecting sync bits in a stream of data bits. Gatlin Gary M., Healy Michael P.; Honewell Inc.

34. Sekimoto Т., Kaneko H. Group Synchronization for Digital Transmission System // IRE International Convention Record, 1962, v. NT-8, part 8.

35. A.C. 300955 (СССР). Способ синхронизации по циклам систем передачи дискретной информации / Колтунов М.Н., Коновалов Г.В., Лангуров З.И.

36. U.S. Patent 5392289. G.R. Varian. Error rate measurement using a com-parison of received and reconstructed PN-sequences. Feb. 21, 1995. Int. CI. G06F 11/00; H04L 12/00; H04L 7/00; H03M 13/00.

37. U.S. Patent 5349611. G.R. Varian. Recovering synchronization in a data stream. Sep. 20, 1995. Int. CI. H04L 007/00; H04L 009/00; H04J 003/6.

38. Корреция ошибок в оптических накопителях информации / Типикин А.П., Петров В.В., Бабанин А.Г.; Отв. ред. Додонов А.Г.; АН УССР. Ин-т проблем регистрации информации. Киев: Наук, думка, 1990. - 172 с.

39. Блейхут Р. Теория и практика кодов, контролирующих ошибки. -М.: Мир, 1986.-576 е.

40. Кларк Дж., мл., Кейн. Дж. Кодирование с исправленеим ошибок в системах цифровой связи: Пер. с англ. М.: Радио и связь, 1987. - 392 с.

41. Касами Т., Токура Н., Ивадари Ё., Инагаки Я. Теория кодирования: Пер. с японского. М: Мир, 178. - 576 с.

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

43. R.J. McEliece. Finite fields for computer scientists and engineers. -Boston: Kluwer Academic Publishers, 1987.

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

45. Лидл Р., Нидеррайтер Г. Конечные поля: В 2-х т. Пер. с англ. — М.: Мир, 1988.

46. B.H. Marcus, R.M. Roth, P.H. Siegel. An introduction to Coding for Constrained Systems // Technical Report No. CS0929, Computer Science Department, Technion* Haifa, Israel, March 1998.

47. B. Marcus, P. Siegel and J. K. Wolf. Finite-state modulation codes for data storage // IEEE J. Select. Areas Commun., vol. 10, no. 1, January 1992. PP. 537.

48. P.H. Siegel. Recording codes for digital magnetic storage // IEEE Transactions on Magnetics, vol. MAG-21, no. 5, Sept. 1985. PP. 1344 1349.

49. J.W.M. Bergmans: Digital Baseband Transmission and Recording. Boston: Kluwer Academic Publishers, 1996. 388 p.

50. K.A.S. Immink. Coding techniques for the noisy magnetic recording channel // IEEE Trans, on Communications, vol. 37, no. 6, May 1989. PP. 243255.

51. Standard ЕСМА-130. Data interchange on read-only 120 mm optical data disks(CD-ROM). 2nd Edition June 1996. http://www.ecma-international.org/publications/flles/ecma-st/ECMA-130.pdf

52. Никамин B.A. Форматы цифровой звукозаписи. СПб.: Элби, 1998.-263 с.

53. K.A.S. Immink. EFMPlus: the coding format of the multimedia compact disc // IEEE Trans. Consumer Electronics, vol. 41, no. 3, August 1995. PP. 491-497.

54. DVD Consortium: DVD specifcations for read-only disc, part 1: physical specification. Version 0.9. April 1996.

55. Егоров С.И., Проценко A.M. Процедура исправления ошибок типа вставок/выпадений бит в каналах передачи цифровой информации // Медико-экологические информационные технологии: Материалы третьей междунар. науч.-техн. конф. Курск, 2000. -С. 136-139.

56. Проценко A.M. Метод исправления ошибок типа вставок/выпадений бит в каналах передачи цифровой информации // Интеллектуальные и информационные системы: Тезисы докладов региональной науч.-техн. конф. Тула: ТулГУ, 2000. - С. 45-47.

57. Проценко A.M. Метод восстановления синхронизации в каналах передачи данных // Новые информационные технологии: Тезисы докладов девятой междунар. студенческой школы-семинара. М.: МГИЭМ, 2001. — С. 63-65.

58. Кнут Д. Искусство программирования, том 3. Сортировка и поиск, 2-е изд.: Пер. с англ. : Уч. пос. М.: Издательский дом "Вильяме", 2000. - 832 с.

59. Проценко A.M. Метод защиты от ошибок в каналах со вставками и выпадениями символов // Новые информационные технологии: Тезисы докладов 10 юбилейной междунар. студенческой школы-семинара. -М. МГИЭМ, 2002. С. 87-89.

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

61. Угрюмов Е.П. Цифровая схемотехника. СПб.: БХВ-Петербург, 2000.-528 с.

62. Карпов Ю.Г. Теория автоматов. СПб.: Питер, 2003. - 208 с.

63. Parnell К., Mentha N. Programmable Logic Design Quick Hand Book. Xilinx Corp., 2002. 201 p.

64. Virtex-II Pro Platform FPGA Handbook Xilinx Corp., 2002. 437 p.

65. Суворова E.A., Шейнин Ю.Е. Проектирование цифровых систем на VHDL СПб.: БХВ-Петербург, 2003. - 576 е.

66. Бибило П.Н. Синтез логических схем с использованием языка VHDL. М.: СОЛОН-Р, 2002. - 384 е.

67. Leung K.S., Welch L.R. Erasure decoding in Burst-Error Channels // IEEE Trans. Inform. Theory. 1981. Vol. 27, no. 2. P. 160-167.

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

69. Попов О.В., Турин В.Я. Оценка распределения вероятности чисел подблоков с ошибками в блоке заданной длины // Передача дискретных сообщений по каналам с группирующимися ошибками . М., 1972. - С. 104113.

70. Box, G.E.P., Muller, М.А. A note on the generation of random normal deviates // Annals of Mathematical Statistics, vol. 29. 1958. P. 610-611.

71. Матвеев В.Ф., Ушаков В.Г. Системы массового обслуживания. — М.: Изд-во МГУ, 1984. 240 с.

72. Jloy М., Кельтон В. Имитационное моделирование. Классика Computer Science. 3-е изд. СПб.: Питер, 2004. - 848 с.

73. Рыжиков Ю.И. Имитационное моделирование. Теория и технологии. — М.: Альтекс, 2004. — 384 с.

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

75. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и ее инженерные приложения. М.: Высшая школа, 2000. 480 с.

76. Гмурман В.Е. Теория вероятностей и математическая статистика. М.: Высшая школа, 2002. - 480 с.