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

РГ б од

ОДЕССКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

г 1 шоп Ю93

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

ИВАНОВ Юрий Дмитриевич

УДК 681.027.8:681.3.053

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

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

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

Одесса — 1993

Работа выполнена на кафедра "Конструирование и производство радиоаппаратуры'' Одесского политехнического университета.

Научный руководитель: доктор технических наук, профеооор

ШКОЛШКО В.У.

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

ПАРАСОЧШ В.А.

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

ПРБШИЦА Г.П.

Ведущее предприятие; ЩИ "Электрон", г.Одесса",

Бапдата диссертации состоится " 30 " иммЛ^ 1993 г. на заседании специализированного Совету К.058Л9.04 Одесского политехнического уяизероатеуа со адресу!' 270044, пр-кт Шевченко, I. *

О диссертацией по%щ ознакомиться ,8 библиотеке ОПУ, Автореферат разослан " Д^" ^¿¡ЛЛ- 1993 г.

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

к.т.н., с.и.о, __—'В.И.КАШЮС

- 3 -

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

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

достоверности данных в ВЗУ на оптических дисках /ОД/ весьма актуальна.

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

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

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

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

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

Для достижения посталвенной цели основные задачи диссертации моино сформулировать следующим образом:

1. Разработась математическую модель источника ошибок в обобщенном дискретном канале.

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

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

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

5. Исследовать вопросы согласования корректирующих свойств кодов с распределением ошибок в канале.

6. Разработать программные и аппаратные средства реализации предложенного метода декодирования сверточных кодов.

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

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

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

I. Разработана.общая математическая модель дискретного'ка-

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

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

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

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

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

Практическая ценнос?$. Разработаны простые практически реализуемые программные я аппаратные средства коррекции ошибок с помощь» сверточнык ко"9VI на основе последовательно-параллельного метода декодирования, обеспечивающие требуемую достоверность информация э реальных каналах внешней памяти ЭВМ при пе-ремежении элементов кодовой последовательности. Разработано декодируй^!? устройство блокового кода с мажоритарным декодированием, вовышающее достоверность информации при переспросе ч каналах внешних накопителей.

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

Основные результаты диссертационной работы использованы при проектировании аппаратуры в СКБ "Молния" /г.Одесса/.

Апробация работы. Основные теоретические положения и результаты диссертационной работы докладывались на УЕ симпозиуме

"Помехоустойчивость и эффективность систем передачи информации" в г.Севастополе /1980 г./; на ХШ Всесоюзной научной сессии, ас-священной Дню радио в г.Москве /1988 г./; на ХХХУП научно-технь-ческой конференции профессорско-проподаватеяъсяого состава и научных сотрудников Одесского электротехнического кксжу?£ свг&Е в 1982 г.; на научно-технических конференциях професссроло-пре-' подавательского состава Одесского политехнического института й 1991-1992 гг.

Публикации. По результатам выполненных исследований олублгзо-вано II' научных работ, получено авторское свидетельство ка изобретение.

Структура и объем работы. Диссертация состоит из введения,. четырех разделов, заключения, изложенных на 166 страницах основного текста, содержит 26 рисунков, таблицы, список ллтера-. туры из НО наименовании и 2 приложения.

ОСНОВНОЙ СОДЕРЖАНИЕ РАВОШ

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

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

о _

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

способы загулты от ошпбох, такие как программные средства, контроль на чстностз, коды, поаразлявЕве одиночные пакеты ошибок не обеспечивая? требуемой вероятности ошибки в накопителях на ОД. Кода, только обнаруаиэавнде ошибки, также малоэффективны из-за наличия неустранимых при повторном считывании ошибок. Однако коды с обнаружением я .«спрзигеяием ошибок достаточно эффективны в система," с переспросе«, поскольку лишь незначительно снижают скорость обмана лнформацаой пол заметном • увеличении достоверности данных.

Асимптотяческя оптимальные метода декодирования сверточ-ншс кодов, к которым относится метод Ватерба, вероятностные методы последовательного декодирования Вэзенкраэта-Фано и Зиган-гкроЕа-Дгеликеко /стек-алгоритм/, позволяют получить достаточно малую вероятность ошибки декодирования при конечной скорости передачи данных. Однако общая сложность реализации■этих методов, определяемая прехде всего объемом памяти и количеством вычислений на декодируемый бит, весьма высока. Поэтому основное внимание в настоящий момент уделяется поиску простых методов декодирования, обеспечивающих достаточно хорошее использование избыточности корректирующих кодов з канале.

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

й т.д. При непосредственном интервально-посимвольном представления параметры модели связаны соотношением рг = V, ' где рц - постоянная вероятность возникновения цепочки паке- . тов; рщ ~ постоянная вероятность возникновения пакетов в пределах цепочки пакетов; - средняя длина цепочки пакетов;

I* - средняя длина пакета; 5^0,5 - вероятность возникновения независимых ошибок в пределах пакета; рв - средняя вероятность ошибки в канале.

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

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

Программа моделирования потока ошибок на ЗШ приведена в приложении к диссертации,.

• При использовании корректирующих кодов достоверность передачи оценивается по вероятности неправильного декодирования кодовой комбинации Р„ . В соответствии с моделью вероятность ошибки кодовой комбинации длины YI при корректирующей способности кода i в канале с определенными параметрами оценивается как

Вероятность Ре(Н) поражения комбинации длины И I и более ошибками определена для случая t =0.

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

Для систем о переспросом, реализующих повторные считывания

информации в каналэх ВЗУ, разработана методика определения оптимальных способов корректирования ошибок. Проведен анализ четырех систем с переспросом при использования блоков х циклических кодов; система А - с обнаруживающим ошибки кодом, система Б - с кодом, обнаруживающим и исправляющим ошибки, система В - о коо-венннм методом обнаружения ошибок и система Г - о косвенным методом обнаружения ошибок и кодом, обнаруживающим ошибки.

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

Р - . п - 1к= Ви

п ^ 1-Р»' Л"« к '

так как. Рм«1 , ю Р„*Рав

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

Для системы Л РщгС„р^ и Р0о '-пр, Здесь р1 =Г(ЬШ) - вероятность ошибки одного элемента в канале с избыточностью как функция отношения сигнала к помехе по напряжению Ь в канале без избыточности и эффективности /? . Так как функция трансцендентная, то прямое вычис-

ление р3 в системе невозможно и в дальнейшем используется обратный метод. При заданной вероятности определяется исходная вероятность ошибки в канале без избыточности р~Р(Н) . Эффективней является та система, дет которой исходная вероятность

р больше при р? =ссшЬ » Вычисления производятся в следующем порядке. Сначала определяется р^ , затем эффективность К .

Далее находится А = 5 и исходная вероятность

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

В системах с косвенным методом обнаружения ошибок

Р»~-Р»£1},

где рн - вероятность ошибки в нестертом элементе; ра - ве-

ошибки

роятность стирания элемента; £ -зона стирания. Для определения помехоустойчивости в этом случае по заданной величина для выбранной зоны £ находят Л , а затем вычисляют рс , R

и исходную вероятность ошибки P'ffî- • систем Б и Г существует оптимальное значение S'Sctt » nP!î котором ~р ~р„,ах .

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

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

Доказана теорема I, согласно которой сверточный код с кодовым ограничением fiÀ -(щ^П, > порождаемый многочленами G (Л) с максимальной степенью 17] и общим числом ненулевых элементов 2k +1» исправляет все ошибки кратности t или менее на длине единичных интервалов'

где tls - число элементов, передаваемых кодером за один такт; M - число единичных тактовых интервалов m +1.

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

nMtCj nW^

во ¿f подпространств, равно 4 , что совпадает с количеством узлов решетчатой, диаграммы, Доказана теорема 2, утверж-. дащая, что из совокупности наиболее правдоподобных путей % , отображающих 2т"' подпространств, всегда можно выбрать один, наиболее .правдоподобный путь пространства %пн на дашне

тактов, отображающий наиболее правдоподобно прост-

ранЖо ХСо на 8Т0Й же Л™116« Ззесь /С, - число информационных элементов, поступающих в кодер за один такт.

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

- II ~

Общае веса.каждого из 5 путей совпадают, т.е.

Условие обнаружения: спабки на такте р состоит в 1 том* тго разрешенные переводы'аз узла отсутствуют. В этом

случае строится кодовое дерево "разбега" для параллельного анализа все:-: возможных путей, которые могут содержать ошибки, подлежащие исправлению. Корень дерева "разбега" необходимо располагать от такта 0 на шагов назад, поскольку па одном такте • коает возникнуть ошибка"кратности п, ■ . Дерево "разбега" ранга М +1 строится на тактах подмножества

Номера путей 2 , проходящих яа такте Ср через ребро ¿(Ср), определяются соотноиекнем

, » > /2/. где 0п - число путей, проходящих через данное ребро на такте Ср , причем для построения дерева ранга М +1 необхо-. диы интервал Ср-О^...^7 ; Я} - общее, число ребер такта Ср ;

¿1 - число узлов такта Ср . Выражения /I/ и /2/ определяют принцип построения дерева "разбега". При.прохождении путей по этому дереву возможно несколько ситуаций.

сер\с)=0 - Здесь общий вес пути 2 па

такте С , СО^Цб)- вес пути Е на такте С . Продвижение пути по разрешенному переходу.

Путь Хм обрывается и принудительно переводится к пути с весом • Принудительный перевод 'гя^С)*°"^/подразу1левает присвоение номеров ребер, принадлежащих пути У- , Еырозденному пути У2П , начиная с такта (р и заканчивая текущим тактом С включительно. Аналогично ооущеотв< ляется присвоение весов. Понятно, что ^(72гг) -

. Организуется локальный "разбег" путей 2р с корнем дерева па текущем такте С , прйчем параллельно . • прослеживаются пути, проходящие по всем, ребрам 2"' , номера которых определяются согласно /I/ для такта разбега Ср »1,

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

торого на такте/'*?- ¿¿^//при минимально необходимом интервале

анализа ¿Г»'заданном теоремой I, однозначно определяет переданный на' этом такте информационный элемент.

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

О - "Г"/1' ¿п г**

/¿-¿Сд^-Д) С

Вероятность стирания элемента рс определена во втором разделе. Декодирующее устройство /рис.1/ содержит входной регаств Г,сумматоры по модулю "два"2, мажоритарный блок 3, выходной регистр 4, переключатель 5, блок обнаружения недостоверных аяегеттов 6, блок формирования сигналов отключения проверок 7, счетчик числа недостоверных проверок 8 и блок формирования сигнала пересяро-са 9» Показано, что подобная комбинированная система со старанием и кодом, исправляющим ошибки и стирания, обеспечивает вдзггрыш в помехоустойчивости по сравнению с одной из лучших систем с переспросом, а именно системой со стиранием и кодом, обнаруживающим ошибки.

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

Разработан аппаратный вариант последовательно-параллельного декодера сверточных кодов, достаточно просто реализованного на основе 6 параллельных вычислителей, обеспечивающего при минимально необходимом объеме памяти и постоянной вычислительной нагрузке вероятность ошибки декодирования, сопоставимую с ошибкой при декодировании с помощью оптимальных методов. Организация работы декодера осуществляется в терминах информационных элементов. Декодер /рио.2/, выполненный на 4 вычислителях, что определяется минимальным количеством прослеживаемых путей на решетчатой диаграмме выбранного кода, состоит из блока канальных элементов I, блоков определения параметров ^ -го пути 2 , блокоп определения пути 3 , блоков памяти Ч и блока вынесения решения 5 .

Ьаа

Рис Л

Рис.2

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

Па

тк

ЫйГ „ .£¿<14

Чц+Чб

м

При достаточно большой вероятности ошибки элемента в пакете 0,3 и длине кодовой последовательности П > Ю максимальный коэффициент повышения достоверности в случае высокой степени пакетирования ошибок рцрщ^РпАможет быть определен в первом приближении из равенства ^т^^Цв • Звдсь Рпа " ве_ роятность не корректируемой кодом ошибки в канале без памяти. Показано, что в исходных каналах накопителей на ОД со средней вероятностью ошибки =1,3'10~4.. .2Ч0"3 короткие коды эффективнее длинных при небольшой кратности корректируемых ошибок

t =1,2 . Максимальные значения коэффициента повышения достоверности tjB =I05...I06 достижимы в каналах-с ре 2'IG""3 при использовании кодов длины П =15,31,63 и кратностью Í =2,3, позволяющих достаточно просто реализовывать оптимальные алгоритмы декодирования.

Разработана методика имитационного моделирования процесса последовательно-параллельного декодирования сверточных кодов в обобщенном дискретном канале с перемещением элементов кодовой последовательности. Согласно методике, вводимая информация преобразуется н кодируется выбранным сверточным кодом с помощью программы M0I), а затем программа K0R осуществляет перемеже- . ние элементов кодовой последовательности. Поток ошибок, организованных программой А'/! в. соответствии с принятой моделью обобщенного дискретного канала, воздействует на канальные элементы. Непосредственнуюреализацию выходной последовательности канальных элементов ñ-AoE=(QtQet,Qi®et, ~,QlQed=(?Í„G1,...,Gt) осуществляет программа КЕ[ . Здесь А и с - двоичные последовательности канальных элементов на входе канала и ошибок соответственно, Программа DEK путем деперемеяения принятой последовательности канальных элементов восстанавливает исходную кодовую последовательность, искаженную практически независимыми, при оптимальном выборе степени перемежения J , ошибками, которая затем декодируется последовательно-параллельным декодером,реализованным программой DCS • Текст программы приведен в приложении к диссертации. Показано, что при.исходной вероятности ошибки в каналах ВЗУ на ОД ре =10~4...Ю~3 необходимое повышение достоверности информации t¡ =10® может быть обеспечено при перемежешш о небольшой степенью J 4 100 элементов кодо-. вой последовательности и сравнительно простом последовательно-параллельном декодировании сверточных кодов с небольшой длиной

кодового ограничения и кратностью исправляемых ошибок £ ¿-2.

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

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

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

2« Разработана обобщенная модель дискретного канала и алгоритм моделирования потока ошибок на ЭВМ, Получены аналитические соотношения, позволяющие оценивать показатели повышения достоверности информации.

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

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

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

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

7. Показана возможность необходимого повышения достоверности данных в каналах ВЗУ на ОД при исходной вероятности ошибки О*. =1СГ^.. и оптимальной степени перемещения в случае использования сверточных кодов о небольшой длиной кодового ограничения и последовательно-параллельного декодирования.

Основное содержание диссертации отражено в следующих публикациях:

I. Иванов Ю.Д. Сравнительная оценка помехоустойчивости систем А30 /Сб,Электрическая связь.-К.:Гехника,19?о.-С.40-46.

2. Иванов Ю.Д., Павлич И.В. Моделирование потока ошибок в дискретном канале на основе принципа сжатия /Сб.научных трудов ОЭИС. Эффективные системы связи.-Одесса,I98S.-С.71-74.

3. Иванов Ю.Д. Декодирование сверточных .кодов.при минимальном объеме памяти /Гез.докл. ,ч.2. XL'Jl Всесоюз.науч.сесс.-М.: Радио и связь, 1988.-С.98-99.

4. Иванов Ю.Д. Оценка помехоустойчивости информации в обобщенном дискретном канале.-Одесса,1993.-4 с.-Деп. в ГНТБ Украины, К JöS^-bri &Л

5. Иванов Ю.Д., Дощечкин А.Е. Последовательно-параллельный метод декодирования сверточках кодов.-Одесса,1993.-6 с.-Деп. в ГНТБ Украины, Je

6. Иванов Ю.Д., Спокойный D.E. Минимальный объем памяти при декодировании сверточных кодов.-Одесса,1993.-5 с.-Деп. в ГНТБ Украины, №

7. Иванов Ю.Д. Оценка помехоустойчивости системы со стиранием и кодом, исправляющим ошибки и стирания.-Одесса,19ЭЗ.-

5 с.-Деп. в ГНТБ.Украины, J§ S'S

8. Иванов Ю.Д., Николаенко В.М. Реализация последовательно-параллельного метода декодирования сверточных кодов.-Одесса, 1993.-4 о.-Деп. в ГНТБ Украины, К ■¿е£Ч"~У:~

9. Иванов Ю.Д. Эффективность корректирующих кодов в обобщенном дискретном канале.-Одесса,1993.-4 с.-Деп.в ГНТБ Украины, Л

10. Иванов Ю.Д. и др. Исследование и разработка дискретной системы радиотелеуправленая внутризаводскими транспортными л. подъемными средствами /Отчет о НИР.-ГР 75033034.-Одесса,1979.

11. А.С, й534039 СССР, МКН Н 04U/00 Декодирующее.устройство /Ю.Ф.Коробов, Ю.Д.Иванов.-Заявлено 30.07.73; 0публ.30.10.76. Бюл. №40.

$0/* /СС Е/.Сь' бЪ