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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБР/ ЗВАНИЮ

КУРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

л _ 'На правах рукописи

РГ6 од

, _ , ЕГОРОВ Сергей Иванович

7 2

УДК 681.327.6.053

АППАРАТНЫЕ СРЕДСТВА И АЛГОРИТМЫ ЗАЩИТЫ ОТ ШИБОК ВНЕШНЕЙ ПАМЯТИ' И ТЕЛЕВИЗИОННОГО КАНАЛА ПЭВМ

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

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

Курск -

1995

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

Научные руководители: • г- .

член-коррёсдондент АН Украины, доктор технических наук, директор Института проблем регистрации информации .

АН Украины Петров В.В; , " . • ''

доктор технических наук, профессор кафедры ВТ КГТу .

Типикин А.П.

Официальные.оппоненты:: доктор технических наук, пр рессор

Переделъснмй Г. И.

кандидат технических наук, начальник отдела телекоммуникации ГУ ЦБ России по Курской области Сусин В.Н.

Ведунья организация - , Ь/ч 25714

Защита диссертации состоится "20" июня 1995 г.' в ф[_1часов на заседании специализированного совета К 064.50.01 по защитам диссертации на соискание ученой степени кандидата технических наук при Курском государственном техническом университете (305039, Курск, ул. 50 лет Октября, 94)

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

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

Автореферат разослан " 1995 г.

Ученый секретарь специализированного совета,.

кандидат технических наук, доцент А ^*^/ В.М.Довгаль

- з -

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

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

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

Эта задача применительно к оптическим накопителям ПЭВМ и телетекстовым системам начала решаться со второй половины восьмидесятых годов и является актуальной до настоящего времени. Сложность решения этой задачи обусловливается жесткими требованиям.! к -объему и цене аппаратуры повышения достоверности при достаточно высоком быстродействии-последней. Важный вклад в решение этой зр-зди. внесли работы Glover N., Shifnan j. (оптические диски). Yamada 0., Mortimer В.(телетекст). При э.том их варианты решения этой задачи опираются на развитую технологию специализированных СБИС. ■ В данной работе предлагаются варианты решения этой задачи; при которых небольшой обьем и невысокая цена аппаратуры повышения достоверности ,достигаются на основе новых вычислительных алгоритмов и архитектурных решений с использованием возможностей современных широко распространенных ВИС и микропроцессоров (МП).. Аппаратура считается экономичной, если она при заданных быстродействии и степени повышения достоверности обрабатываемой информации обладает сравнительно небольшой сложностью.

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

. Г- ч.'

ма информации без снижения скорости ее передачи.

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

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

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

- соадание экономичных быстродействующих микропроцессорных декодеров (МП-декодеров) PC-кодов;

- создание пошаговы декодеров с минимальными затратами аппаратуры

- создание помехоустойчивых устройств синхронизации СЗО;

- создание СЗО оптических накопителей информации для ПЭВМ и цифровых вещательных, телевизионных каналов.

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

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

Z. Доказана 'новая теорема о взаимосвязи компонент многочлен; остатка от деления кодового слова на многочлен, порождающий РС-ко;

3. Созданы на основе доказанной теоремы новые вычислительны! алгоритмы пошагового декодирования■PC-кода и декодеры с неполны вылавливанием ошибок, снижающие дополнительные аппаратные затрат; СЗО контроллеров внешней памяти и адаптеров телевизионного канала

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

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

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

На основе результатов диссертации созданы:

- о -

1. Специализированные экономичные устройства кодирования и вычисления синдромов (УКВС)', позволяющие значительно ускорить процедуру исправления ошибок микропроцессорными декодерами.

2. Экономичный пошаговый декодер PC-кода с неполным, вылавливанием ошибок.

3. Микропроцессорная СЗО со встроенным УКВС для накопителей на лтических цилиндрах.*

4. СВО вещательной системы распространения компьютерной информации (АСРКИ-2) по телевизионным каналам с использованием секционных .микропроцессоров.

Реализация и внедрение результатов работы. Созданная на основе результатов диссертационной работы микропроцессорная СЗО оптических .накопителей (с УКВС-1) встроена в контроллеры ЕС5153.0001, ■ ' разработанные, в НИИСВТ (г.Киров).

Созданная на основе -результатов диссертационной работы СЗО данных, передаваемых по' телевизионному каналу, встроена я адаптер ЕС8180, который выпускался серийно Киевским ПО "Зигектронмаш", Киевским радиозаводом, Смелянским радиоприборным заводом в 1991 1992 годах (в 1'991г. было• выпущено 1500 устройств), и используется а автоматизированной системе распространения компьютерной информации по телевизионным каналам,' разработанной и реализованной в Ш1РИ АН Украины. •

Апробация работы. Основные .положения диссертационной.работы докладывались и обсуждались на: Всесоюзной научно-технической конференции "Развитие теории и техники хранения информации" (г. Пенза, 1983 г.);.- областной научно-технической конференции "Проблемы, перспективы создания и внедрения САПР, ГПС, АСУ на промышленных предприятиях " (г.Курск, .1987 г.); Всесоюзной научно-технической конференции "Проектирование внешних запоминающих устройств на подвижных носителях" (г. Пенза, 1988г.); 2 республиканской научно-технической конференции "Функционально-ориентированные вычислительные системы" (г.. Алушта, 199Q г.); Международной научно-технической, конференции .г^птико- слектронные приборы и устройства в системах распознавания образов, обработки изображений и. символьной информации", (г. Курск, 1993 г.).

Публикации. По материалам' диссертации опубликовано работ, в том числе .4 авторских свидетельства и-патент. *

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

- 6 - .

страницы основного текста, 45 рисунков и 23 таблицы, а также списка литературы из 139 наименований на 15 страницах и девяти приложений на 81 страницах.

На защиту выносится:

1. Теорема о взаимосвязи компонент.многочлена, остатка от деления кодового слов на многочлен, порождающий РС-код.

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

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

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

5. Последовательные по символам УКВС, позволяющие значительно повысить производительность'микропроцессорных декодеров РС-кодов, при минимальных дополнительных аппаратных затратах.

6. Алгоритмы и экономичные устройства помехоустойчивого установления блочной синхрогчзации СЗО в контроллерах ВЗУ.

7. Микропроцессорные СЗО контроллеров оптических накопителе! ЕС5153 и адаптеров вещательной системы распространения компьютер ной информации ЕС8180 по телевизионным каналам.

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

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

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

Отмечается, что в информационных трактах оптических накопит' лей (ОН" информации дефекты носителя вызывают, кроме ошибок опо

нания, ошибки синхронизации. •

Для характеристики ошибок на входе СЗО в диссертации используются величины Peo (вероятность ошм^.-л в бите) и РСо (вероятность ошибки в символе). Рбо для большинства ОН ограничена сверху величиной 1Q"4 на бит. При приеме информации в приемниках телетекста Pso зависит от места расположения приемника и доходит до Ю-3.

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

N6 = N6n/Pc6, (1)

где Нбп - количество информации пользователя в блоке и Pcs - вероятность сбоя в блоке. Величина Pcs может быть оценена следующим, образом:' ,

' max <Phsc-, Р(М1Е)>. < Рсб < Рнбс + Р(НОШБ), (2)

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

Для рассматриваемых компьютерных систем Ng должно ыть не менее 1012. Поэтому необходимо, чтобы

Рнбс < N6n*10_12 и Р(НОШБ) < Ыбп*1СГ12. (3)

Выполненный обзор известных методов защиты от ошибок показал, что основным методом защиты от ошибок в ОН и системах распространения информации по телевизионным каналам является коррекция ошибок с применением PC-кодов над конечным полем GF(2!n).

Показано, что требуемую степень достоверности воспроизведения информации в ОН обеспечивает только совместное применение РС-кодов с большим кодовым расстоянием d>13 (РСБКР-кодов) и средств восстановлении синхронизации. В системах распространения информации по телевизионным каналам наши применение PC-коды с малым d<6.

В' конце главы формулируются требования к аппаратуре повышения достоверности информации, основными блоками которой являются декодеры РС-ком'-эв и уе-ройства-групповой синхронизации (УГС). Основное требование к.аппаратуре CQO периферийных устройств ПЭВМ - экономичность. В диссертации аппаратура считается экономичной, если она при заданных быстродействии и' степени повышения достоверности обрабатываемой информации обладает, сравнительно небольшой' сложностью." Предлагается использовать две меры сложности аппаратуры. Первая предусматривает характеристику аппаратуры парой коэф-

- 8 - , фициентов л в к*п> которые обозначают соответственно число вентилей И-НЕ и число ячеек памяти (ОЗУ и ПЗУ), требуемых для реализации аппаратуры. Вторая мера сложности аппаратуры, используемая в диссертации, представляёт собой число-г м стандартных универсальных СИСИ БИС, требуемых для-реализации-аппаратуры. , ■

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

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

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

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

2(а-1)(п-1), . если У=0

26 + 6 + 2(сЗ-1)(п-1), если

4с1 + 26 + 2(<3-1)(п-1), ' если \>=2 (4)

6с1 + 68 + 2(сЫ)(п-1), . если у=3 ' •

4. 5у2+ (2с)+2п+1.5)у + 2(с1-1) (п-1), если где п - число символов в кодовом слове (КС). Зависимость получен; при реаг-зации 1-го этапа процедуры по схеме Горнера, 2-го - т алгоритму Берликэмпа-Месси, 3-го - по методу Ченя для больщог числа ошибок и табличному методу при числе*ошибок С, 4-го - п Методу Форни. - .

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

(V)

Т1э1 = 2(d-l)(n-1) '

т\Э2 * 0.5a2 +' 2(d+l)a '

Чэз * 2na - e~aC2na + (2n - 2.5)a~ + (n - 3.8)a3]. (5) * 4a2 + 2a .

!)э5 * 2a,

где a=n*Pco, ii3i - сложность i-го этапа процедуры декодирования.

Выполненный на основе полученных формул анализ сложной^и декодирования РСБКР-кодов показал , что для каналов с РСо<10~3 среднее значение, сложности существенно меньше значения максимальной алгоритмической сложности, и подавляющую часть средней алгоритмической сложности процедуры декодирования составляет сложность этапа вычисления синдромов.'

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

Предлагается вариант структурной организации МП-декодера РСБКР-кодов (рис.1) для контроллеров ВЗУ с конвейерной обработкой секторов, основанный на использовании экономичных пошаговых декодеров для коррекции до 2-х-ошибок. Благодаря аппаратной реализации вычисления синдромов и коррекции небольшого числа ошибок значительно повышается средняя скорость программного вычисления на МП значений большего числа ошибок. Для РС-кода (76,64) над полем GF(23) и МП типа Intel 8088 с тактовой частотой 4.5 МГц она превысит 1300 Мбит/с при Рсо<10~3, а для каналов с более высоким уровнем ошибок Рсо=;6*Ш-3 средняя скорость достигает 9 Мбит/с.

Предлагается вариант структурной организации экономичного МП-декодера ГСБКР-кодов (рис.2) для контроллеров ВЗУ с последовательной обработкой г кторок. предусматривающий использование УКВС. Для оценки влияния его характеристик на производительность ВЗУ с последовательной обработкой секторов в контроллере вводится коэффициент потери производительности

£ = Тснл/Тсн ' С®)•

где- Тен - минимальное время считывания всей информации с полностью записанного- носителя без СЗО, ТСнд - математическое ожидание Ере-

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

V Рис.1

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

'РИС. 2

СТРУКТУРНАЯ СХЕМА УКВС-1.

Сч 1

Сч

Шина адреса

Шина, дан

Ш

РгВ'

РгА •

' -1

См

РгС

ПЗУ

к

Рис.3

- ■ ! - 11 - • ' мени считывания 'всей информации с нос».-е ля с использованием СЗО (ТСнд) при последовательном обходе дорожек. ' • \

■ Выводится выражения•для в:

е = Хс/Хс'+ксдАс' £ (Í+mFl((Í+l)to6+tc-toH6-tnK6) - (V) .

¿*0

" Fl(to6+tc_toH6-tnKs)]. где Хс- глубина чередования секторов с CSD; Хс'- глубина чередования секторов в подсистеме памяти без СЗО; ксл - количество секторов на дорожке; tOHe - время загрузки буфера; tone -(.время выгрузки данных из буфера в ПЭВМ; t0e - время одного оборота'диска; tc -период прохождения секторов, упорядоченных по номерам,■ под оптической головкой; Fi(t) - функция распределения случайной величины Тд6 (времени декодирования буфера); ri - наибольшее целое, не превосходящее частное от деления максимального значения Гл6+Ь0нб+Ьпкб -tc на tos- '

Выполненные расчеты е показывают, что производительность ВЗУ при встраивании в контроллер декодера с У ИБС, реализованного на Ш типа Intel 8088 с тактовой частотой 4.5 МГц и использующего РС-код (76,64) над полем GF(28), в области реальных вероятностей ошибок уменьшается не более, чем на 42 при Рсо<10-3.

Приведены структуры, описаны принципы работы и характеристики созданных экономичных последовательных по символам УЮ;С РСБКР-кодов. УКВС реализуют кодирование и вычисление синдромов с учетом вычисления синдромов по следующим рекуррентным формулам:

,i-< _Í „С п *

Ч*. 3 - 41-1.^5^2-; 4^=0, 411.0-0, 1=0,(1-2, 3-0,Х-1, (8) ЫЭ,к-1, ' . ' '

где з обозначает 1-ую компоненту 3-го остатка от деления на порождающий многочлен кода Б(х) Ь первых символов информационной части з-го кодового слова, - коэффициенты 6(х), 1*= 1к-1-ъ. з + Яё-2.3. и } - символ информационной части 3-го кодового

слова, и ' ' - •

° ¡*аь+1 + Гп-1-ъ.>; =0, 1-673=2, (9)

ЫЭ,п-1,

где Гп-1-ъ.л " символ а-го кодового слова, $ - 1-ая компонента 3-го синдрома после обработки I первых снмвг-зов л-го кодового слова, й - примитивный элемент~ поля. В основе структуры УКВС-1 (рис.3) лежит общая шина. Обработка одной компоненты синдрома осуществляется за'три такта. Коэффициент его аппаратной сложности ра-• вен£м=б1, что значительно,меньше коэффициента сложности известного по патенту США параллельного УКВС (гМ"=131 без учета схем. управ-

ления" и интерфейса). Предложена конвейерная структура УКВС-2, быстродействие которого увеличивается почти в три раза по сравнению, с УКВС-1 при незначительном повышении сложности до<*м=63.

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

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

Формулируется теорема'о взаимосвязи любых трех компонент многочлена остатка от деления ассоциированного многочлена КС.на Б(х) при наличии единственной ошибки в , информационной части КС.

• Теорема. Если в кодовом слове Рида - Соломона произошла одна ^'«ибка и она расположена-в .информационной части, то. любые три компоненты многочлена остатка связаны следующад соотношением:

При наличии в информационной части кодового слова'любых двух ошибок соотношение (10) не имеет место. В (10) обозначает^коэффициент ' многочлена. остатка при х1, ¿-коэффициент многочлена Ё(х)=0(х)/(х-аь"1).

На основе классического метода вылавливания ошибок и найденной- в диссертации свя;-... между коэффициентами, многочлена остаткоЕ вводится применительно к РС-кодам новый класс декодеров с неполнш Еылавливанием ошибок.. , „ ■" ' .

, Доказывается корректность ; следующего алгоритма нахождения значения озибки У в младшем'разряде кодового слова -РС-кода с Ф5:

1. Если иКд(х))=0 ошибок в принятом слове нет й У=0.

2. Если и1(ч(х))<2', то все ошибки в контрольной части, либс их число больше двух, и У^о- 4

3. Проверяем справедливость соотношения'(10) для 41-

Если соотношение не выполняется (г*0>, . значит/в -разряда)

п-1,....1 кодового слова произошло не менее двух ошибок, и У=0.

•• | ' - 13 -

Если соотношение выполняется (г=1), то вычисляется значение Яо' при.1=0, о=2, 1=3 по следующей формуле: \

ео(а3+а2) . ' •

Ч^еза3 (а°+а2) ^Бг«2 (ос°+л3) ,

и У=яо-до'.

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

!0, если иЬ(д(х))=0 .

ао, если иг(дд(х)к2

О, если иЬЫхтг и.г=0 .

Чо-до* , если и т=1

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

Описываются разработанные автором новые пошаговые декодер:»' РС-кода с неполным вылавливанием ошибок, основанные на до.лзаннсй теореме. В том числе - пошаговый декодер с минимальней задержкой декодирования и параллельной обработкой многочлена остатков, исправляющий один или два ошибочных символа в слове РС-кода и обнаруживающий дополнительные ошибки, который предназначен для введения в МПСЗО ВЗУ с целью повышения ее производительности. Пошаговый декодер допускает "экономичную аппаратную реализацию при использовании таблиц для выполнения нелинейных операций в конечных полях. Коэффициенты аппаратной сложности КЛС (для РС-кода с <1=5) равны <*в=22*пн-15 и ¿еп=6л2т«71 и снижены по сравнению с агв=54-Ат+2'!и агп=8*2п,лш созданного ранее в КГТУ простого пошагового декодера.

Приведены структура и описание работы созданного экономичного пошагового декодера с последовательной, обработкой многочлена остатков и минимальным коэффициентом сложности зг м=20 для РС-кода (15,11) над полем (ЗР(24). При тактоЕ'й частсте 4 МГц декодер работает на потоке данных, передаваемых со скоростью 500 кбит/с.

В четвертой главе анализируются методы и устройства групповой синхронизации в ВЗУ; разрабатываются алгоритмы помехоустойчивого установления блочной синхронизации; создаются экономичные устройства помехоустойчивой синхронизации'. ,%',• . ..,.-

Выполненный анализ показал, что существующие УГС либо не обеспечивают достаточно надежное установление синхронизации, . либо недостаточ: : экономичны. ■

При использовании заголовка с дублированием маркеров значительное повышение надежности установления блочной синхронизации (Рнбс^'Ю-12) при использовании несложной аппаратуры обеспечивает применение предложенного алгс лтма с пороговым решением. Сущность. алгоритма заключается в накоплении информации о начале блока данных в массиве счетчиков, инкрементировании всех счетчиков массива на каждом такте (один такт соответствует одной позиции заголовка) и проверке попадания р или большего числа счетчиков 'в финальное состояние (финальное состояние соответствует началу блока данных).. Приводятся структура и описание работы устройства обнаружения начала блока данных (УОНБД), реализующее алгоритм.

Экономичную аппаратную 1 реализации обеспечивает предложенный алгоритм установления блочной синхронизации по рекуррентной последовательности имен маркеров. Сущность- предложенного алгоритма заключается в предварительном установлении синхронизации по первому обнаруженному маркеру и проверке правильности установления синхро-* низации по следующим (г-1).маркерам: Если (г-1) следующих маркеров -.^дтверждают правильность предварительной установки синхронизации, синхронизация устанавливается окончательно. Если хотя бы один из следующих маркеров не подтверждает правильность предварительно установленной синхронизации, то тогда- по нему снова предварительно устанавливается синхронизация и осуществляется проверка по следующим (г~1) марксфам. Алгоритм предусмат !вает применение помехоустойчивого кодирования имен маркеров, необходимого для обеспечен^ максимального расстояния по Хеммингу между зачетными участками рекуррентной последовательности имен. . Используются слова смежной класса расширенного кода Хэмминга (п-,к) = (8,4) (табл.), обеспечива при применении восьми маркеров Рнес =2*10~12 в ДСКБП с. РйО=1074.

Сложность созданного на основе алгоритма устройства У0НБД-: (рис.4) меньше сложности известного по патенту'США. простого УОНЕ на 45 вентилей (¿*в=45) и -*м=13 при" 1>2. При увеличении г выигры в сложности значительно увеличивается. На основе уонВД-2 ' создан экономичное (*м=20) УГС для подсистем оптической памяти. УГС лег и, сопрягается с МП-декодерами и обеспечивает Исправление многотага них сбоев тактовой синхронизации. :

Пятая глава посвящена рассмотрений конкретных7СЗО, создали

СТРУКТУРНАЯ'СХЕМА' УОШД-2.

ДВх

ТИ

СБРОС

D Рг1

С

Сел1

ССА

П

БСК

КС

дкк

ДВых

К1' Рг2

Dn Сч2

Ü1 +

Dv-i

Y

С

R

Рис.4

Таблица

Слова смежного 1100 0010 0010'1010 .010 0001 0001 - -0011

класса расширен- ООН 1101 1101 0101 0101 1110 1110 1100

ной кода Хэм- 0000 0100 0100 1001 1001 1000 1000 1111

минга 1111 1011 1011 0110 ОНО 0111 0111 0000

на основе теоретических результатов диссертации:- микропроцессорной СЗО (МПСЗО-1) накопителей на оптических цилиндрах для персональных компьютеро ЕС5153; микропроцессорной СЗО (МПСЗО-З) вещательной системы распространения компьютерной информации ЕС8180. .

Разрабатываются кодовые конструкции форматов хранения и лере-дачи информации СЗО. . Рассматриваются^структуры й-работа СЗО. Приводятся результаты аксперимёнтального исследования■СЗО на стендах и в реальных каналах. ' .

Описываются процедуры имитационного,моделирования СЗО, необходимые для вычисления на ЭВМ вероятностных характеристик СЗО в широком диапазоне ^вариации параметров ошибок. Процедуры предусматривает моделирование источника ошибок в канале передачи информации, и моделирование обработки' ошибок собственно СЗО на ЭВМ. . >

Иссле-ования показали, что созданные МПСЗО обеспечивают значительное повышение достоверности воспроизведения и приема информации даже при cpáвнигeльнa высоких вероятностях ошибки на бит в канале.Рбо = Ю~3 - 5*10"3 , обеспечивая требуемую достоверность .в области, реальных вероятностей ошибок.

В приложениях приведены: структуры и описание работы УКВС-2 и Ш-декодера на секционных. микропроцессорах, исходные данные для р_чсчета сложнбсти устройств,, исходные тексты программ коррекции ошибок и исследования вероятностных характеристик СЗО,'доказательство теоремы, протоколы испытаний СЗО, акты и справка о внедрении результатов научных исследований.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ Р/ ЭТЫ ' •

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

2. Предложены для контроллеров ВЗУ прямого-доступа с последовательной и конвейерной обработкой секторов схемы структур быстродействующих экономичных. МП-декодеров со встроенным устройством кодирования и вычисления синдромоЬ (УКВС) или 'аппаратным пошагово, декодером. Благодаря введению дополнительного параллельного пошагового fleKOflepá, исправляющего двэ ошибки, средняя^скорость Ш-де-

. ' - 17 -

кодера (1гЛе18088) повышена до 32 Шит/с ..ри Р<^<10~3 по сравнению с 6.7 Мбит/с, достигнутыми МП-декодерам (1пЬе18088) со встроенном УКВС (85С20), и с 8.1 Мбит/с, возможными при программной реализации декодера на быстродействующих микропроцессорах (1п1е1586). .

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

, денйя РСо<Ю~3.

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

5. Предложен алгоритм установления блочной синхронизации по рекуррентной последовательности имен маркеров заголовка сектора данных, основанный на кодировании имен словами смежного класса кода Хемминга и проверке предварительно установленной синхронизации путем анализа последующих маркеров и обеспечивающий- достижение значения вероятности неустановления синхронизации не более 2*10~12 в области частот ошибок воспроизведения до 10~4 на бит при сравнительно невысокой сложности устройств £м=13...20.

6. Созданы: . '

- пошаговый декодер РС-кода (15,11) над.полем (ЗР(24) .с минимальной аппаратной сложностью «=20, встроенный в адаптер цифрового теле-, визионного канала и работающий в реальном магитабе времени на скорости передачи 500 кбит/с;

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

' 18 -ВЗУ и имеющий аппаратную сложность &м=120;

- микропроцессорная система зашиты от ошибок для контроллеров оптических' накопителей ЕС5153.0001 с использованием последовательного УКВС-1, ' обеспечивающая гарантированное исправление пакета ошибок размером до 1559 бит в секторе данных 2 Кбайта;

- микропроцессорная СЗО системы распространения компьютерной информации по' телевизионным .ке тлам, встроенная в адаптер ЕС8180 и повышающая достоверность приема -информации путем исправления до двух сшибок или четырех стираний-в каждом из кодовых . слов . и при соответствующем перемежении их символов - до двенадцати строк.(384 бит) в кадре. ' .

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

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

, 1, Типикин А.П., Взбанин А.Г.> Гвоздев В.В., Егоров С.И. Быстродействующее" устройство зашиты ВЗУ от ошибок, исправляюще« Йва. пакета ошибок, в кодовом слове // Рагвитие теории и. техник! хранения информации: Тез. докл. / Всесоюзная науч.-техн. конференция, 'г. Пенза, 6-8 сент. 1983 г. --М.: Радио-и связь, 1983 -С. 45-4?. . .' ■ • .

,2. Типикин А.П., Бабанин А.Г., Е' ров С.И., Пеньков А.Г Принципы построения. системы сбора и обработки данных об ошибка внешних запоминающих устройств // Алгоритмы и структуры,- специали зированных вычислител! ых систем: 'Межвуа. сб. науч. тр. / МВСС РСФСР. Тульский политехи., ин-т. -Тула: ТЛИ, 1984. "С.111-116.

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

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

5. Новиков В.А., Типикин А.П., Егоров С.И. Устройство испра

ления ошибок в НМЛ кодом Рида-Соломона // Вопросы . ради,электрони--ки. Сер.ЭВТ: Науч.-техн. сб./'НИЙЭИР:'• 1986. - Вып. 5. - С.79т90.

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

7. Егоров С.И. Программная реализация декодера помехоустойчивого кода Рида-Соломона на однокристальной шкрр-ЭВ^' серии 1816 для исправления ошибок в ВЗУ // Проблеш, перспективы создания и внедрения САПР, ГПС, АСУ на промышленных предприятиях: 'Тез.' докл. '/ Областная научно-техническая конференция, г. Курск, 16 дек. 1987 г. - Курск: Курский областной'совет НТО, 1987. - С.'26-27.

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

9. A.c. 1381719 СССР, МКИ4 Н 03 М 13/00. Устройство обнаружения и исправления ошибок в кодах Рида-Соломона / А.П.Типикин, В.В.Петров, Н.В.Горшков, В.В.Гвоздев, С.И.Егоров (СССР). - N 4061423/24-24; Заявлено 28.03.86; Опубл. 15.03.88, Бюл. N10. -10с.

10. Егоров. С.И.Применение микропроцессорных декодеров кода Рида-Соломона для коррекции ошибок в малогабаритных оптических накопителях // Проектирование внешних запоминающих устройств на подвижных носителях: Тез. докл. / Всесоюзная научно-техническая конференция, г.Пенза, 8-9 сент.1988г. -Пенза: ПДНТО, 1988. - С.22-24.

11. Егоров С.И., Петров В.В.,. Типикин А.П., Гвоздев В.В., Х<аксимов O.A. Корректирующий ошибки адаптер телевизионного широковещательного канала информационной сети ПЭВМ // Функционально-ориентированные вычислительные системы: Тез. докл. / 2 республиканская науч.-техн. конференция, г. Алушта, 4-6 октября ,1990 г.- -Харьков: ХПИ, 1990. - С.33-34.

12. Егоров С.И. Специализированный процессор-декодер кодов Рида-Соломона // Функционально-ориентированные вычислительные системы: Тез. докл. / 2 республиканская науч.-'техн. конференция, г. Алушта, 4-6 октября 1990 г. - Харьков: ХПИ, 1990. - С.33.

13\ Егоров С.И. О программно-аппаратной реализации декодеров кода Рида-Соломона для защиты от ошибок малогабаритных оптических накопителей./ Курск, политехи, ин-т. - Курск, 1990. - 39с.: ил., табл. -Виблиогр.26 назв. - Деп. В ЮИОРШРИБОР 10.09.90 К48§8-пр90.

14. A.c. 1656689 СССР, МКИ4 H 03 M 13/00,.13/02. Устройство кодирования и вычисления синдромов- помехоустойчивых кодов для коррекции ошу/ 1К во'внешней памяти ЭВМ / С.И.Егоров, А.П.Типикин,

B.В.Петров, А.В.Гостеэ (СССР). - N 4722202/24-24; Заявл. 26.06.89; Опубл! 15.06.91, Еш.-N 22, -7с.

15. Егоров С.И. . Декодер Меггита для исправления ошибочных символов в файлах изображе' я с применением кодов Рида - Соломо-. на.// Оптико-электронные приборы и- устройства в системах, распознавания образов, обработки изображений и символьной информации: Материалы конф./ Международная- научно-техническая конференция,, г. Курск, 5-8 октября 1993 г. - Курск: Курский политехи.'ин-т, 1993г. -С.194 -195. - ,'

16. Пат,. 2024966 PS; МКИ5 G 11 В 27/10, 20/18. Устройство для определение начала блока данных во внешней памяти 1 О.А.Максимов,

C.И.Егоров, А.П.Типикин, А.С.Вачевских, В.М.Лукибанов -(Россия).' -N 5022512/10; Заявл. 02.07.91; Опубл. 15.12.94, Вол. N 23, - 12с.

Соискатель . '. . ' С.И.Егоров

Подписано к печати' 1I04. 45 . Формат 60 к 84 1/16

Печатных листов ■', f 6 Тираж 100 экз; Заказ

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