автореферат диссертации по радиотехнике и связи, 05.12.21, диссертация на тему:Разработка методов и устройств идентификации и коррекции ошибок кодами Боуза-Чоудхури-Хоквингема

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

) I

3 ОД

УДК 621.391 и !

Власова Галича Атексаидрсшка

РАЗРАБОТКА МЕТОДОВ И УСТРОЙСТВ ИДЕНТИФИКАЦИЙ И КОРРЕКЦИИ ОШИБОК КОДАМИ БОУЗА-ЧОУДХУРИ-ХОКВИНГЕМА

05.12.21 - Радиотехнические системы специального назначслик, включая тгхкиху СБ'! и технологию их производства

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

Минск 1996

Работа выполнена в Белорусском государственном университете информатики и радиоэлектроники

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

профессор Кона не ль ко В.К.

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

доктор технических наук, профессор Чердыниев В.А., кандидат технических наук, доцент Югцезпч М.М.

Оигюнирухяшм! организация

НПО "Агат1

Защита состоится 6 июня 1996 г. в 14 часов на заседании совета ае защите диссертаций Д.02.15.02. в Белорусском государственном университете информатики и радиоэлектроники по адресу; 220027, Минск, ул.П.Брзъки,

С диссертацией можно ознакомиться в библиотеке БГУИР. Автореферат разослан 6 маг! 19% г.

Ученый секретарь

совета по защите диссертаций

к.т.к., доцент

Саяоматин С.Б.

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

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

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

Связь работы с научным» программами. темами. Тема диссертационной работы является составной частью тематики научно-исследовательских работ, проводившихся в ходе выполнения ГБЦ 92-3086 "Разработать конструкторско-схемотехнические методы повышения надежности и качества СБИС и устройств На их основе", ГБЦ 93-3003 "Разработать конструкторско-схемотехнические методы построения микроэлектронных устройств, устойчивых к отказам и сбоям элементов", ГБЦ 96-3092 "Разработка методов и средств кодовой защиты систем передачи и хранения информации от ошибок и несанкционированного доступа".

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

Поставленная цель определила следующие основные задачи:

1. Развитие методов обнаружения, идентификации и коррекции ошибок.

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

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

Методы исследований: понятия, методы и результаты теории передачи информации, теории кодирования, теории полей Галуа, матричной алгебры, полиномиальной алгебры, комбинаторики, алгебры логики, схемотехники БИС и дискретных устрой« в; технические методы, включающие компьютерное моделирование .

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

1. Предложены методы разделения ошибок произвольной кратности на классы подмножеств, характеризующиеся весом ошибок, расстоянием между ошибочными разрядами, и идентификации ошибок БЧХ-кодами по множеству параметров {Ыг).

2. Предложены и развиты методы построения устройств для параллельного и пошагового декодирования БЧХ-кодов с идентификацией ошибок. Показано, что использование метода идентификации ошибок при перестановочном декодировании позволяет упростить поиск множества подстановок, достаточных для декодирования БЧХ-кодов.

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

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

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

Разработанные алгоритмы нашли применение при разработке цифрового телефона и в учебном процессе в дисциплине "Прикладная теория кодирования".

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

Йсцощые__рщо2У£1ЦЩ_ДЦ£С£ШйЦИЦО£ИМНа Защиту:

1. Метод разделения ошибок на классы подмножеств, характеризующиеся весом ошибок, расстоянием между ошибочными разрядами, и метод идентификации ошибок БЧХ-кодами по множеству параметров (Ы7(.

2. Методы построения устройств для Параллельного и пошагового декодирования БЧХ-кодов, основанные на идентификации ошибок и перестановочном декодировании кодов.

3. Модифицированные БЧХ-коды для коррекции двойных независимых ошибок и модульных ошибок длины три, четыре, и быстродействующее устройство их декодирования на вентильных матриц-

Личный вклад соискателя. В совместных работах участие научного руководителя носит постановочный характер, а лично соискателем разработаны методы разделения ошибок на классы подмножеств, идентификации ошибок БЧХ-кодами, Методы построения устройств параллельного и пошагового декодирования, коды для совместной коррекции двойных независимых ошибок и модульных ошибок длины три, четыре.

работы докладывались и обсуждались на 3-ей международной научно-технической конференции "Современная технология гибридных интегральных микросхем, включая элементы сверхпроводниковой электроники" (Нарочь, 1994 г.); Научной конференции, посвященной 30-летию деятельности коллектива БГУИР (Минск, 1994 г.); Научно-технических конференциях "Направления 1} перспективы развития микроэлектронной элементной базы, электронных блоков И узлов, устройств индикации и считывания для приборостроения, аудио- И видеотехники, оистем связи и информатики" (Минск, 1994 г.), "Микроэлектроника в медицине, автомобиле- и тракторостроении, системах и устройствах охраны, наземного н кабельного телевидения, космической и оптоволоконной связи" (Минск, 1994 г.); Международной научно-технической конференции "Современные средства связи" (Нарочь, 1995 г.), 1 Республиканской научно-технической конференции "Состояние и перспективы развития вооружения и военной техники" (Минск, 1994г.).

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

Структура и объем диссертации. Диссертация объемом 147 страниц состоит из введения, рбшей характеристики работы, четырех глав, выводов,

списка использованных источников, приложений, в том числе основной текст - 88 страниц, 11 таблиц, 26 рисунков - 21 страница, список использованных источников (95 наименований) и шесть приложений - 38 страниц.

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

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

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

Среди известных методов декодирования БЧХ-кодов по синдрому выделяются алгебраические методы и пошаговые. Алгебраические методы декодирования основаны на определении по синдрому многочлена локаторов ошибок а(г) и нахождении его корней. В работе проводится анализ следующих основных методов нахождения коэффициентов о(г) и его корней: определительный метод, метод исключения неизвестных (метод Гаусса), алгоритм Берлекэмпа-Месси, алгоритм Евклида; процедура Ченя, прямой метод. Основные трудности при декодировании связаны с определением вектора ошибок по синдрому. Показано, что реализация устройств коррекции многократных ошибок требует значительных аппаратурных и временных затрат. Эти затраты связаны с построением селектора для анализа всевозможных г- разрядных комбинаций синдромов (гаг^, где х\ - число проверочных разрядов кода, исправляющего одиночные ошибки, I - кратность исправляемых ошибок). Снизить затраты на схемы коррекции позволяет применение однородных кодов, проверочная матрица которых содержит однотипные столбцы или подматрицы. Однородные коды позволяют, кроме того, проектировать устройства обработки с регулярной однородной структурой и высоким быстродействием. Однако, устройства с подобными свойствами для коррекции многократных ошибок (1>2) не известны.

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

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

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

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

В соответствии с методом разделешм ошибок на классы подмножеств, каждое подмножество состоит из (п-1) циклического сдвига образующего: (О, e||]j, е$„.......где efjjj- номера разрядов 0, 1, 2, ..., (п-1)

последовательности длины п. Подмножества характеризуются лесом ошибок, расстоянием между ошибочными разрядами. Число подмножеств ошибок кратности t равно С'п/П' Показано, что применение метода разделения ошибок на классы подмножеств позволяет уменьшить сложность селектора в t раз при последовательном декодировании циклических кодов с использованием регистров сдвига и в п раз при реализации декодера на ПЗУ.

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

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

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

Предложен метод идентификации ошибок произвольной кратности БЧХ-кодами по множеству параметров (Nz}, исключающий чередование мультипликативных и аддитивных операций и содержащий минимальное число последовательных шагов. Показано, что разделение ошибок на классы подмножеств позволяет ввести в таблицу смежных классов множество параметров {Nz}. Правило формирования N2 определяется видом проверочной матрицы Н кода. Пусть проверочная матрица Н кода, корректирующего t ошибок имеет вид:

H=laa,i. aaji> - ■ aaiilT,iH0,n-lJ. Каждый элемент рассматриваемого множества {Nz} представляет собой линейную комбинацию двух элементов множества {a;, ie|l,...,tlj.

Действительно, элементы синдрома S=(S|, S2,....., S,)T=(ctx' ,а"2, ... ,ctx')T

последовательно изменяются в подмножестве ошибок соответственно на aj, а?, ..., а,. Следовательно, величины N1=(a1X2-a2X|) mod п,

N2=(ajX3-ajX|) mod п, ...»

4 Nu=(a(t.1)xt-alx(t.i)) mod n , остаются постоянными в подмножестве. Тогда подмножество класса ошибок

кратности 1>1 характеризуется множеством {Nz, ze(1,..., и]}, где u= Ct •

Метод идентификации ошибок по множеству параметров {NJ заключается в определении по синдрому S значений Xi, xj, ..., xt и вычислении значений Nz, ze[l, ..., и], однозначно определяющих подмножество ошибок. Метод позволяет идентифицировать вес ошибки, расстояние между ошибочными разрядами, а также принадлежность ошибок к соответствующему подмножеству с заданными свойствами. Показано, что выигрыш по сравнению с методами, основанными на свойствах многочлена локаторов ошибок, тем выше, чем больше кратность идентифицируемых ошибок.

Дополнительный выигрыш при обработке БЧХ-кодов можно получить, если исключить операции умножения на константу aj. Пусть а"1 элемент поля Галуа OFi(2m) с порождающим полиномом гп('<(х)

(аЯ| является примитивным элементом этого поля). Элемент синдрома а"2 можно рассматривать не только как элемент поля GF|(2m), но и как элемент эквивалентного поля GF2(2m) с порождающим полиномом т<2'(х) и примитивным элементом а3'. В этом случае степени xj и х, элементов а

синдрома S* =(Si*, S2',...... St')T=(<%x,*,aXj*, ... ,ax,*)T последовательно

изменяются в подмножестве ошибок в одном направлений на (+1). Каждое подмножество ошибок при этом характеризуется множеством параметров {Nj} , ze (!,•••, и], причем ' Ni=(x, - xj) mod n, ( N2=(xj - X3) mod n,

i Nu=(X(,_i)-xj) mod n . Третья глава работы посвящена разработке методов построения устройств декодирования БЧХ-кодов с идентификацией ошибок. Показано, что множество параметров идентификации ¡Nz), рассмотренное выше, может быть использовано для синтеза устройств декодирования БЧХ-кодов, корректирующих многократные ошибки.

В общем случае образующему k-го класса t-кратных ошибок (ej{J ,

...... ef>1)k)( где -ef0>>k = ^, е^-е^Л?, е?',,-

е(!*-2), соответствует синдром Sg^ia*''' > ax'»'1 — > ax"')T-

Пусть , ax'l> )T -с!ШДром 5-Го элемента данного

Подмножества (e^+Ö, . е'^ +3). Тогда, в

соответствии с методом идентификации ошибок, степени х[к), х^, ..., синдрома 5-го элемента подмножества являются сдвигами степеней

'о

*?>, ■••, синдрома образующего (с учетом параметров проверочной матрицы): x|k) = xW + a,8, х^к)= а25..... х<к) = х<к) + а,5. Отсюда

е(0)к +5 = e(gt- ^ + .... e[i-i)t (е^ + Е^'На -

*<"> v№) х!к)

t—1 X ' * X

Ве~ Ы e(0)t +

х(к) , . *<к>

1 I \ г\ I

> •••> ^(t-i), - e{o)t + Z Д i[ - постоянны для каждого

подмножества ошибок, могут быть вычислены заранее и храниться в ПЗУ. Метод построения устройств декодирования БЧХ-кодов, задаваемых проверочной матрицей вида H=|aai', а"2'» — » аа,11г> ie|0,и-1] заключается в следующем:

1. вычисляется синдром S =(ах', а*!. •••> аХ| )т;

2. определяются величины X), X2, ..., xt;

3. вычисляются значения параметров N|=(aiX2-a2X|) mod n, N2=(a|Xj-ajX|) mod n, .... , N11=(a(l.|)xl-atx(,.i)) mod n (определяется подмножество ошибок);

4. по значениям {Nz} блок анализа (ПЗУ) определяет значения £ок, 5ik..... S(t-i)k (емкость ПЗУ Q=( £ (cj, / n)x i) x m);

5. по значениям 4o > £lk < — > £(i-l)k и x)/al определяются номера

ошибочных разрядов.

Аппаратурные затраты на реализацию метода составляют:'

Q=

1,875 • t • m n + t + t • mi5,75 + i icj,/ ii] - ^^ - 0.5m + n + 1 V 2 ¡-J J 2

* q, где

4 - сложность двухьходового сумматора по модулю два. Сложность предлагаемого устройства для кодов, корректирующих двойные ошибки, примерно в два раза ниже сложности одного из лучших известных устройств. При реализации устройства декодирования БЧХ-кода по рассмотренному методу время обработки составляет порядка 10 задержек на вентиль. Показано, что дополнительны/! выигрыш в сложности реализации можно получить, если исключить блок умножения элементов М на константу а,.

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

В работе развит метод построения устройств декодирования БЧХ-кодов на вентильных матрицах с идентификацией ошибок. При коррекции 1-кратных ошибок устройство декодирования состоит из I дешифраторов

элементов синдрома Э = (а*1,«*1,«"3.....а*' )т, г вентильных матриц

(матрицы 1, 2, ..., 0-1) определяют значения множества последняя

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

„2"

0 =

,.2т-|ИГ+(,-1).х " +

2 ' Х2 4 ' 2

П - 1 , , т

——+ Ы = 2 2 . , *2 = 2Ш И > ^

I л

где *1 =

х Ч,

О 4 в 2

¡'1

Быстродействие устройства коррекции определяется числом последовательно соединенных элементов (дешифратором, задержками на двух вентильных матрицах И блоком анализа), состаачяет т=4 задержки на вентиль (в случае 1-2 - т=3) и не зависит от длины кода п. Рост кратности корректируемых ошибок 4 и длины кода п приводит к соответствующему увеличению числа вентильных матриц И их размеров.

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

всех £ С'"1, комбинаций ошибок с единицей в старшем разряде. 1=1

Разделение ошибок на классы подмножеств И введение в декодер цепи модификации синдрома позволяют использовать сокращенное число

селектируемых комбинаций, а именно Т С'п /. В этом случае достаточно

1=1 7,1

селектировать синдромы образующих подмножеств ошибок. Сложность

' I г 1 I

селектора уменьшается в £ С' , / ( £С|,/п) г I раз. При подобном выборе ¡=1 п~' ¡=1

селектируемых комбинаций коррекция ошибок БЧХ-кодамн происходит Не более, чем за (2п+е|^_цввх) тактов (или (Зп-Тп/(Г) тактов). Показано, что

при пошаговой обработке реверсивных БЧХ-кодов имеется возможность дальнейшего уменьшения на 0,5 п тактов Бремени декодирования (за счет учета того, что кодовое слово реверсивного кода, прочитанное в обратном

направлении, также принадлежит коду). Аппаратурные затраты при этом практически не возрастают.

Следует отметить, что при пошаговой обработке БЧХ-кодов значения параметров {Nz} в явном виде не определяются, и класс ошибок не идентифицируется (данный параметр несложно определить, например, с помощью ПЗУ). При определенном циклическом сдвиге синдром принятой последовательности совпадет с селектируемым синдромом образующего соответствующего подмножества ошибок.

В работе развит метод построения последовательно-параллельных устройств декодирования БЧХ-кодов с использованием идентификации ошибок. Для кодов, корректирующих t - кратные ошибки, задаваемых порождающим полиномом g(x) = inM(x)x,n'2'(x)*—xmW(*)> в течение первых и тактов информация заносится в буферный регистр и одновременно вычисляются остатки от деления принятой последовательности v(x) на каждый сомножитель порождающего полинома S, = Rm(i,(X)lv(x)l=r(,)(x) (синдром S = (S|, S2, ..., S,)T). Последовательно соединенные дешифратор элементов, поля, сумматор по модулю п и блок анализа множества параметров (Nz) определяют дополнительные затраты на декодирование. При реализации этих блоков на вентильных матрицах, вносимая ими задержка х « и. Выигрыш в быстродействии обусловлен исключением вычислений в поле GF(2ra) (нахождение многочлена локаторов ошибок), а также процедуры Ченя, реализуемой за 11 тактов.

В работе проведен анализ множеств подстановок, относительно которых код инвариантен или переходит в эквивалентный код, и устройств перестановочного декодирования БЧХ-кодов. Исследовалась группа G*n , содержащая циклические подстановки и подстановки вида U*p : о~>ро (mod п), где р - число взаимно простое с п ( общее число таких подстановок-<р(п), в случае простого п - <р(п)=(»-1) ). Среди подстановок вида и*р m являются подстановками вида fJJ: а->2'ш (mod п), сохраняющими код, остальные переводят код в эквивалентный. Показано, что использование подстановок, переводящих код в эквивалентный, позволяет расширить множество кодов, допускающих перестановочное декодирование, а применение метода идентификации ошибок дает возможность упростить поиск множества подстановок, достаточных для декодирования БЧХ-кодов.

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

кодов заключается в соответствующем расположении столбцов матрицы Н на длине кода.

Доказана теорема 1: Код с проверочной матрицей Н1П=[М0 |М4„ |Мц], где

ма1- м ^ аи1 а2и,| м I а1"« а31-1 а31-1! , _п/,

полученный перестановкой столбцов проверочной матрицы н Г1 а о? ... Г» а а2 ... ^ с^1 ... а^1'

[1 а5 а6 ... «Н [| а3 а6 ... а31-3! 1 а5 ... а", 1 а3 ... а*-3 БЧХ-кода с с1=5 ( а- примитивный элемент поля Галуа ОР(2ш) и т- четное, шг4), исправляет двойные независимые ошибки и одиночные модули ошибок длины три.

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

в проверочной матрице Н БЧХ-кода с <1=5 выделяются три последовательные однотипные секции длины 1_=п/3;

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

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

В работе рассматриваются методы построения однородных кодов (частным случаем однородных кодов являются реверсивные БЧХ-коды, задаваемые проверочной матрицей Н=|а',а"',1|т), обеспечивающих совместную коррекцию двойных независимых ошибок и одиночных модулей ошибок длины четыре.

Пусть НШ1=( Ь|П1) И2т, 1]т- проверочная матрица (2Ш, 2Ш - 2ш - 1)-кода, полученная из матрицы Н реверсивного БЧХ-кода перестановкой столбцов (разрядов кодового слова) по правилу: а'"'-и (¡=11, 2, ..., 2Ш -11, нулевой столбец остается на месте). В результате, столбцы подматрицы 111т (элементы поля Галуа ОГ(2т) ) представляют собой т-разрядные двоичные числа 0, 1, 2, ..., 2га -1, расположенные в лексикографическом порядке. Столбцы матрицы Нт) последовательно разбиваются на. 2т'2 модуля длины четыре.

Доказана теорема 2: код, задаваемый проверочной матрицей Нть корректирует двойные независимые ошибки, а также одиночные модули ошибок длины Ь>=4 и пакетные ошибки длины р=3.

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

столбцы подматрицы проверочной матрицы Н=| Ь), Ьз, 1 1Т реверсивного БЧХ-кода, рассматриваемые как т-разрядные двоичные числа, располагаются в лексикографическом порядке;

столбцы полученной подматрицы Ь1т рассматриваются как элементы а1 поля ОР (2,п);

подматрица Ьгш формируется на основании 1)|т согласно правилу построения реверсивного кода: а'-кг!;

столбцы полученной матрицы Нт[ =|Ь|т , 1|2т , 1 ]Т последовательно разбиваются На 2т"2 модуля длины четыре.

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

а) представим степени 1" ненулевых элементов а' поля Галуа ОР(2ш) (т-нечетное) в виде таблицы:

1 5 9 13.....п-10 п-6 п-2

2 6 10 14.....п-9 п-5 п-1

3 7 11 15.....п-8 п-4 0 '

4 8 12 16.....п-7 п-3

б) первую строку полученной таблицы циклически сдвигаем на 2 позиции, а третью строку - на 1 позицию:

9 13.....п-2

2 6 .....п-9

7 II.....п-4

А 8 .....п-7

Элементы первого столбца полученной матрицы Н,^ образуют первый модуль, второго столбца- второй модуль и т.д. Правило формирования последних двух модулей (один из которых - неполный) зависит от длины кода п. В проверочной матрице Н „д= (И^,*, 1)2т*1 кода, корректирующего двойные независимые и модульные ошибки длины четыре, столбцы подматрицы Ь2т* есть обратные элементы к столбцам 11|т*. Для предложенного метода формирования реверсивного кода расчеты на ЭВМ показали, что синдромы модульных ошибок веса и 3 различны и не

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

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

(Зд0П=| 1,625п + 0,5т + 3 | х я, что составляет примерно 5% от затрат на реализацию устройства декодирования двойных ошибок на вентильных матрицах. По быстродействию данное устройство превосходит известное устройство коррекции двойных независимых и одиночных модулей ошибок длины четыре примерно в два раза. Эго достигается за счет уменьшения числа последовательно соединенных элементов, регулярной и однородной структуры устройства.

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

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

2. Предложены и развиты методы построения устройств параллельного декодирования БЧХ-кодов с идентификацией ошибок. Показано, что при использовании регулярных и однородных структур (вентильных матриц) время обработки составляет не более 4 задержек на вентиль и не зависит от длины кодовой последовательности.

3. Развит метод построения устройств пошаговой обработки БЧХ-кодов. Показано, что метод разделения ошибок на классы подмножеств позволяет уменьшить сложность селектора в I раз, повысить быстродействие на 1 п/|Г тактов для БЧХ-кодов и на (0.5п+1 пДГ) тактов для реверсивных кодов.

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

5. Развит метод построения последовательно-параллельных устройств декодирования БЧХ-кодов с использованием идентификации ошибок. Показано, что при последовательном приеме сообщения, вычислении синдрома и дальнейшей параллельной обработке синдрома возможно Повышение быстродействия за счет исключения вычислений в поле ОИ (2га) (нахождение многочлена локаторов ошибок), а также реализуемой за п тактов процедуры Ченя.

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

7. Разработано устройство декодирования однородного кода, исправляющего двойные независимые ошибки и одиночные модули ошибок, на вентильных матрицах, характеризующееся высоким быстродействием, • приемлемыми для практической реализации аппаратурными затратами, однородной структурой. Это достигается благодаря преобразованию однородного кода в БЧХ-код со стандартным расположением столбцов в проверочной матрице и введением небольшого числа дополнительных логических элементов для анализа трех- и четырехкратных ошибок в модулях.

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ

1.Власова Г.А., Копопелько В.К. Устройство декодирования на базовых матричных кристаллах// 3-я международная НТК "Современная технология гибридных интегральных микросхем, включая элементы сверхпроводниковой электроники": Материалы конференции,- Нарочь, 1994,- с.181-184.

2. Власова ГЛ. Коррекция двойных и модульных ошибок однородными кодами// Научная конференция, посвященная 30-летию деятельности коллектива БГУИР: Тезисы докладов. Ч.1.- Мннск, 1994.- с.53-54.

3.Власова ГА. Последовательная обработка циклических кодов, корректирующих многократные ошибки // Информационный листок Белинформпрогноз. Серия 20.53,- 1995.

4.Власова Г.А. Устройствб коррекции двойных и модульных ( шибок реверсивными кодами // Информационный листок Белинформпрогноз. Серия 50.39,- 1995.

5.Власова Г.А., Конопелько В.К. Гибридное декодирование циклических кодов, корректирующих многократные ошибки// Направления и перспективы развития микроэлектронной элементной баэы, электронных блоков и узлов, устройств индикации и считывания для приборостроения, аудио- и видеотехники, систем связи и информатики: Тез. докл. науч.-техн. конф,- Минск, 1994.- с.42.

6.Власова Г.А., Конопелько В.К. Разработка БИС для обнаружения и коррекции ошибок в микроэлектронмых структурах// Отчет по НИР "Разработать конструкторско-схемотехнические методы повышения надежности и качества СБИС и устройств на их основе", ГБЦ 92-3086, N ГР 01920014617,- Минск, 1992.- 116 с.

7.Власова Г.А., Конопелько В.К. Идентификация ошибок при передаче информации с корректирующими кодами// Международная НТК "Современные средства связи": Материалы конференции.- Нарочь, 1995.-с.36-38.

8.Власова Г.А., Конопелько В.К. Синтез корректирующих кодов со специальными свойствами Устройства для декодирования// Отчет по НИР "Разработать конструкторско-схемотехнические методы построения микроэлектронных устройств, устойчивых к отказам И сбоям элементов ГБЦ 93-3003, N ГР 1994470,- Минск, 1993,- 69 с.

Э.Власова Г.А., Конопелько В.К. Совместная коррекция одиночных байтов и двойных ошибок однородными кодами в интегральной памяти // Микроэлектроника в медицине, автомобиле- й Тракторостроении, системах и устройствах охраны, наземного и кабельного телевидения, космической и оптоволоконной связи: Тез. докл. науч.-техн. конф,- Минск, 1994,- с.26.

¡О.Положительное решение на выдачу пате1!та РФ по заявке №5036221/24 от 23.09.94г. "Устройство декодирования для Коррекции тройных ошибок" /Конопелько В.К., Власова Г.А. д,

/Уу

РЭЗЮМЭ

Власава Галша Аляксандра?на, распрацо?ка метада? 1 устройства)? шэнтыф1каиы1 I карэкцьп памылак кодам1 Боуза-ЧоУдхуры-Хоквшгэма, выявление, ¡дэнтыф1кацыя, карэкцыя, БЧХ-коды, кодавая адлегласиь, кратнасць памылк!, праверачная матрица, Ындром, таблща сумежных . класа?, апаратурныя I часовыя затраты, пераста?леныя пераутварэнш, незалежныя памылш, грутруючыеся (модульныя) памьит, аднароднасць, вентыльныя матрицы, В1С карэкцьи памылак.

Для змяньшэння затрата? пры дэкадз1раванш БЧХ-кода? распрацаваны метали раздзялення памылак на класы падмноства? 1 ¡дэнтыф1кацьи памылак. Падмноствы памылак характарызуюцца вагай памылак, адлегласцю памйж плмылковым1 разрадам1. Для ¡дэнтыф1кацьп памылак БЧХ-кодам1 ?водзщца мноства параметра?

Прапанаваны 1 разв1ты метады пабудовы хуткадзейных паралельных устройства? апрацо?м БЧХ-кода? з аднароднай структурай, устройства? пашатовай апрацо?ю са скарочаным наборам селекшруемых камбшацый, устройства? паслядо?на-паралельнай апрацо^и. Праведзены анал|'з мноства падстановак ! устройства? перастановачната дэкадз1равання БЧХ-кода?. Паказана, што выкарыстаине шэнтыфжацьм памылак дазволщь выключыць переборны характер выбару патрабуемьгх падстановак. Прыводзяцца значэнш апаратурных I часовых затрата? на дэкадзфаванне БЧХ-кода?.

Распрацаваны метад пабудовы мадыфкаваньтх БЧХ-кода?, карэкшруючых двайныя незалежныя памылю ! адэпючныя модул! памылак да?жыш тры 1 чатыры. Распрацавана хуткадзейнае Устройства для карэкцьй двайных 1 модульных памылак на вентыльных матрицах. Выкарыстаине подобных кода? 1 устройства? апрацо?к1 дазволщь пашырыць тал!'ну прымянения В1С карэкцьп памылак.

РЕЗЮМЕ

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

Для уменьшения затрат при декодировании БЧХ-кодов разработаны методы разделения ошибок на классы подмножеств и идентификации ошибок. Подмножества ошибок характеризуются весом ошибок, расстоянием между ошибочными разрядами. Для идентификации ошибок БЧХ-кодами вводится множество параметров (Nz).

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

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

RESUME

Vlasova Galina Alexandrovna, (he development of techniques and devices of error identification and correction by Bose-Chaudhuri-Hocquenghem codes, detection, identification, correction, BCH codes, code distance, error order, check matrix, syndrome, adjacent classes table, apparatus and time expenses, permutation transformations, independent errors, grouped (module) errors, uniformity, gate matrix, LSI error correction.

To minimize the expenses while decoding BCH codes the techniques of dividing errors into subset classes and error identification were developed. Error subsets are characterized by the error weight, the distance between the erroreus digits. A number of (Ыг) parameters are introduced by BCH codes to identify errors.

The techniques to build quick-processing concurrent BCH code devices with uniform structure, the devices of step-by-step processing with the reduced Set of selected combinations, subsequent-concurrend processing devices were suggested and developed. A substitution sets and the devices of BCH code permutation decoding were analysed. It was shown that the use of error identification will

enable to eliminate the sorting character of the required substitution selection. The values of apparatus and time expenses on BCH code decoding are given..

The technique of building modified BCH codes able to correct double independent errors and single length error modules 3 and 4 were developed. The quick-processing device to conect double and module errors on the gate matrices was developed. The use of such codes and processing devices will enable to expand the LSI error correction application.