Устройство для обнаружения и исправления ошибок кодом Рида-Соломона Советский патент 1988 года по МПК H03M7/18 H03M13/00 

Фл

00

Is:)

I Изобретение относится к электрон- ijibJM дискретным устройствам систем Автоматики, телемеханики и вычисли- tenbHoft техники и предназначено для 1(спользования в системах передачи и Хранения информации, где возможно возникновение нескольк.их пакетов ошибок.

Цель изобретения - повьгаение быст- Содействия устройства. i На чертеже представлена блок-схе- Ца предлагаемого устройства. I Устройство содержит блок 1 посто- 1НИОЙ памяти адресов перехода, счет- шк 2, блок 3 постоянной памяти уп- )авлякяцих сигналов, блок А буферной памяти, арифметико-логический блок 5, блок 6 постоянной памяти, блок 7 бу- (ферной памяти, информационную шину 8, :Тактовый вход 9,шину 10 управления переходом, вход 11 управления, шину 112 сигналов состояния, шину 13 адреса перехода на новые управляющие сигна- |лы, адресную шину 14, шину 15 управ- {ляющих сигналов и двунаправленные I шины 16-18.

Если сигналы данных поступают по ;шинам 8 и 16 из блока 5, то результат вьщается по шинам 17 и 18 в блок 7, I и, наоборот, если сигналы операндов I поступают из блока 7 по шинам 17 и I 18, то табличный результат передается I по шинам 8 и 16 в блок 5. Двунаправ- 1 пенная передача сигналов по шинам 8,16-18 дпя блока 6 осуществляется чере мультиплексоры. Блок 7 предназначен для приема, оперативного хранения. и выдачи по двунаправленные шинам 17, 18 промежуточных значений сигналов. Блок 4 предназначен для хранения принятого слова, поступающего по дву- . направленной шине 8.

Устройство работает в дзух. режимах; кодирования и декодирования.

Кодирование осуществляется путем деления информационного слова на порождающий многочлен

q(x) (х®1)(х©с,)(х@ оС)...(хФоб ).50

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

Cj,® С , Х®С,Х2© . . J®C; X ® . . 61С ,

где С; - i-й - символ информационного

слова.

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

q(x) .

Вычисление остатка от деления по правилу деления многочленов сводится к следующим формулам:

С-, Cj., ® ;

, - с.,,«

;

Cj. с,-., ,

Cj, С,-.4®С;о(,%

где С; 4 последний пришедший символ .

Декодирование начинается с вычисления синдромов по схеме Горнера

С;©8„5

S,- G;©S,ci ;

84 С;®8,,Л ;

Sj- C;®8jet.,

где С - i-й символ информационного

слова;

ti - примитивный элемент поля. После вычисления синдромов 8, 9, 8j, 8 проверяется их равенство нулю, если все 8; О, то ошибок нет и блок 3 вьщает по шине 15 управля- кяций сигнал на вьщачу информационного слоя во внешнюю систему. Если все , то возможна одна ошибка и проверяется дополнительное условие

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

, ,,

где L - место ошибки.

Если равенство не выполняется, то происходят две ошибки. Если боль ше одного S; О, но не все S О, то количество ошибок больше двух и устройство отказывается от исправле ния. Если происходят две ошибки, то значения и адреса ошибок находятся из решения системы уравнений, которая для случая двух ошибок имеет вид:

с ; ® с;,

cici ®Cjo6

cU (

/2J -; oi

Sj OL

42932А4

При умножении элемента поля Галуа на const, сигналы, соответствующие значению элемента, поступают на вход блока 6, для которого они являются -

5 адресами, по которым записаны коды, соответствующие значению элемента, умноженного на const, где i и j - адреса ошибок; С1 и Cj - значения ошибок. Исправление происходит по фор- 0 муле

С; .

где С; - неисправленный символ;

5 С- - исправленньй символ.

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

20 по принципу один символ в одно слово, следующий во второе и т.д.

Изобретение относится к авто- .матике и может применяться в системах с электро1Л Ыми дискретными устройствами передачи и хранения информации, где возможно возникновение пакетов ошибок. Устройство решает задачу обнаружения и исправления ошибок с использованием кода Рида-Соломона упрощенными средствами, существо которых состоит в том, что все операции при кодировании и декодировании сводятся к ограниченному набору операций: сложения по mod 2, сложению, вычитанию и использованию табличных методов, таких как таблицы логарифмов, антилогарифмов, умножения на const, извлечения корней уравнения. Устройство содержит блок постоянной памяти адресов перехода 1, счетчик 2 блок постоянной памяти управляющих сигналов 3, блок буферной памяти 4, арифметико-логический блок 5, блок постоянной памяти 6, блок буферной памяти 7, информационную шину 8, тактовьй вход 9, шину управления пе- Щ реходом 10, вход управления 11, шину сигналов состояния 12, шину адреса перехода на новые управляющие сигналы 13, адресную шину 14 управляющих сигналов 15, двунаправленные шины 16, 17, 18. 1 ил. (Л

где SQ, S,, Sj, S:j-.вычисленные

. синдромь ; , с и

9i

- значения-ошибок; и J - адреса ошибочных

символов;

of. - примитивньй элемент поля Галуа.

Решая эту систему уравнений, дят значения ошибок С; и С| и адреса неисправленных символов i и j. Вычисления производятся без использования умножителей и сумматоров по модулю основания кода. Для вычисления используется свойство, по которому каждьй элемент можно представить как степень примитивного элемента поля су вГ , где Cj - j-й - элемент поля; i - степень примитивного элемента.

В поле заданы две операции: сложение по mod 2 и умножение. Операция умножения сводится к сложению степеней примитивного элемента. При умножении двух элементов поля Галуа сигналы, соответствующие значению каждого элемента, поступаю,т на входы блока 6, для которого они являются адресами таблиц логарифмов. По этим адресам записаны коды, соответствующие показателям степеней примитивных элементов. Эти коды поступают -на вход арифметико-логического .блока 5, где они складываются, и результат поступает на вход блока 6 (таблицы антилогарифмов) , по которому считываются сигналы, представляющие значение результата умножения двух элементов.

25 с

С г г г г О1 - О7 11 {1 t

i Т. .

где С- - информационньй символ, идущий в первое слово; С - информационньй символ,

30 идущий во второе слово.

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

35 ошибок без его услож1йения.

В режиме кодирования на вход 11 управления поступает признак кодирования (уровень 0), который совместно с кодовыми комбинациями, поступающим

40 по шинам 10 и 12 соответственно из блоков 3 и 5, является адресом выбора из блока 1 начального адреса ко дирования, поступающего по шине 13 на счетчик 2. Со счетчика 2 по шине

45 14 адрес без изменения вьздается в блок 3, по которому в нем записаны управляющие сигналы выполнения перво операции, результатом которой явля- ется обработка первого информаци50 онного символа. Первьй информационньй символ по информационной шине 8 поступает в блок 5, откуда без изменения записывается через блок 6 в .

55

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

: Дальнейшую работу рассмотрим на примере обработки (i-A)-ro информационного символа. Перед приходом (i-4)-ro информационного символа в б|пок 7 записаны вычисленные ранее , (1-1)--й, (1-2)-й, (1-3)-й симво- По информационной шине 8 (1-4) -й символ поступает в блок 5. Из блока 7 по шине 17 и 18 поступает С; на вход бпока 6, Он является адресом, по которому записан результат умножения С; Xui. Из блока 6 этот результат по шине 16 поступает в блок 5, где ПРОИЗВОДИТО.Х операция сложения по mod 2. Результат операции поступаеч го шине / или 18 и записьтзется без изменения в блок 7.

Управление описанным процессом

1ычислепня осуществляется управляющи- сигкглами, поступающими по шине 15

3 блоха 3, Аналогично вычисляются

Оьые иа 1е1гая С , С4-, С;. Если в блок 5, где происходит их сложение, поступивший (1-4)-й симрол последний, 25 Результат, сложения из блока 5 по шине to вновь вычисленные символы C,-.j , 8 или 16 поступает на вход блока 6

как адрес таблицы антилогарифмов.

Считанное значение записьшается по

4-1 являются контрольными ш-гаолами инфэрмадт онногс слова, соторые поступают из блока 5 по шине ё во внешнюю систему.

шине .17 ияи 18 в блок 7. Аналогично 30 вычисляется S, Для проверки-равенства полученные значения считываются из блока 7 в блок 5, где происходит сложение по mod 2. В зависимости от результата операции соответствующий

В режиме декодирования, по шине 11 поступает уровень логической 1, bti6op начального адреса режима декошине .17 ияи 18 в блок 7. Аналогично 30 вычисляется S, Для проверки-равенства полученные значения считываются из блока 7 в блок 5, где происходит сложение по mod 2. В зависимости от результата операции соответствующий

ирования аналогичен режиму кодиро- код поступает по шине 12 на вход ания. По шине 8 в устройство посту- блока 12 и происходит формирование Ьает информационное слово с контроль- нового адреса втравляющих сигналов.

Найденный адрес неисправного символа поступает по шине 17 в блок 4, откуда

ными символами. Первый символ без изменений записывается в блок 7. Рассмотрим вычисления синдромов S, S,, 40 неисправньй символ по шине 8 поступа- 8,83 с приходом i-ro символа. В

блоке 7 записаны вычисленные ранее значения , S, S, S. По информа- :ционной шине 8 i-й символ поступает в блок 5. Из блока 7 по шине 17 или 18 предыдущее значение синдрома поступает на вход блока 6, где оно является адресом таблицы умножения синдрома на соответствующую const. Вычисления производятся по описанной схеме Горнера. В блоке 5 производится операция сложения по mod 2 над пришедшим символом и ранее вычисленным синдро мом, умноженным на const, поступившим по шине 16 из блока 6, Результат вычисления записЬгвается в блок 7. Значение операций блока 5, выбор таблиц в блоке 6, выбор адресов в блоке 7, направление передачи определяются

ет в блок 5, где происходит корректировка по формуле

С{ cf © с,

45

где С; - неисправленный символ, поступивший из блока 4; С{ - значение ошибки, поступающее из блока 7 в блок 5; С; - исправленный символ.

50

55

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

932A6

управляющими символами, пocтyпaкш и fl . из блока 6 по шине 15,

С приходом последнего символа заканчивается вычисление синдромов, и е начинается определение возможного количества ошибок в информационном слове. Для проверки на равенство нулю синдром из блока 7 записывается в блок 5, В зависимости от того, равен

10 он нулю или не равен, по шине 12 . соответствующая кодовая комбинация выдается с выхода блока 5 на вход блока 1, и происходит формирование нового адреса управлякяцих сигналов.

15 Для проверки равенства, например. So X S. S J 5,и S считываются из блока 7 соответственно по шинам 17 и 18 и поступают на вход блока 6, где они являются адресами таблицы

20 логарифмов. Из блока 6 считанное из адресов таблицы логарифмов значение степеней примитивного элемента поступает по шинам 8 и 16 соответственно

шине .17 ияи 18 в блок 7. Аналогично вычисляется S, Для проверки-равенства полученные значения считываются из блока 7 в блок 5, где происходит сложение по mod 2. В зависимости от результата операции соответствующий

40 неисправньй символ по шине 8 поступа-

ет в блок 5, где происходит корректировка по формуле

С{ cf © с,

45

где С; - неисправленный символ, поступивший из блока 4; С{ - значение ошибки, поступающее из блока 7 в блок 5; С; - исправленный символ.

50

55

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

Формула изобретения

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

блока постоянной памяти, второго блока буферной пагАЯТН и арифметико-логического блока, выход которого соединен с вторым входом первого блока постоянной памяти, третий вход которого является входом управления устройства, первьй и второй входы-выходы третьего блока постоянной памяти соединены с первыми выходами-входами

соответственно арифметико-логического

блока и второго блока буферной памя

ти, третий вход-выход третьего блока .

постоянной памяти соединен с вторым

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

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