Устройство для обнаружения и исправления ошибок кодом рида- соломона

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1 (191 ®U (Ill (5D4H ОЗМ 13 00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

H АВТОРСКОМУ С8ИДЕТЕЛЬСТВУ (21) 4105341/24-24 (22) 02,06.86 (46) 07,10.88. Бюл. 9 37 (72) Е.И.Мартыненко. Т.Ф.Аверьянова, В.ТаГулько и В,И.Пономарчук (53) 621.394.14(088,8) (56) Авторское свидетельство СССР

У 1381719, кл. Н 03 М 13/00, 27.02.87.

: (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ И

ИСПРАВЛЕНИЯ ОШИБОК КОДОМ РИДА-СОЛОМОНА (57) Изобретение относится к автоматике и может применяться в системах с электронными дискретными устройствами передачи и хранения информации, где возможно возникновение пакетов ошибок. Устройство решает задачу обнаружения и исправления ошибок с использованием кода Рида-Соло. мона упрощенными средствами, существо которых состоит в том, что все операции при кодировании и декодировании сводятся к ограниченному набору операций: сложения по mod 2, сложению, вычитанию и использованию табличных методов, таких как таблицы логарифмов, антилогарифмов, умножения на

const, извлечения корней уравнения, Устройство содержит блок постоянной памяти адресов перехода 1, счетчик 2> блок постоянной памяти управляющих сигналов 3, блок буферной памяти 4, арифметико-,логический блок 5 блок постоянной памяти 6, блок буферной памяти 7, информационную шину 8, тактовый вход 9, шину управления ne- Q реходом 10, вход управления 11, шину сигналов состояния 12, шину адРеса (Л перехода на новые управляющие сигналы 13, адресную шину 14 управлякщих сигналов 15, двунаправленные шины

16, 17, 18. 1 ил.

1429324

ЫС; х Q+ +.. O+ +Ñ„õ", Со С,xO+C х О+

C; - С;,®С,, "; с;» - с„ес;ы тв, С;», - C; 4®С;<

s0 C%e S0

S С®8 g

Изобретение относится к электронным дискретным устройствам систем автоматики, телемеханики и вычислиТельной техники и предназначено для

Использования в системах передачи и

5 хранения информации, где возможно возникновение нескольких пакетов ошибок.

Цель изобретения - повышение быст- 1р родействия устройства.

На чертеже представлена блок-схеМа предлагаемого устройства.

Устройство содержит блок 1 посто-! иной памяти адресов перехода, счетик 2, блок 3 постоянной памяти упавляющих сигналов, блок 4 буферной памяти, арифметико-логический блок 5, .!блок 6 постоянной памяти, блок 7 бу,:ферной памяти, информационную шину 8, 2р тактовый вход 9,шину 10 управления переходом, вход 11 управления, шину

:,12 сигналов состояния, шину 13 адреса, перехода на новые управлякицие сигна,: лы, адресную шину 14, шину 15 управ,:ляющих сигналов и двунаправленные шины 16-18, Если сигналы данных поступают по шинам 8 и 16 иэ блока 5, то результат, выдается по шинам 17 и 18 в блок 7, 3п и, наоборот, если сигналы операндов поступают из блока 7 по шинам 17 и

:; 18, то табличный результат передается

, по шинам 8 и 16 в блок 5. Двунаправ1

:ленная передача сигналов по шинам

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

Блок 4 предназначен для хранения принятого слова, поступающего по двунаправленной шине 8.

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

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

q (x) = (х & 1) (х9 о ) (х® оа )... (х Э о ) Я где С; — i-й - символ информационного слова.

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

4 в тв

Вычисление остатка от деления по правилу деления многочленов сводится к следующим формулам: с; с„ ас, ы, 1 где С;„ - последний пришедший символ.

Декодирование начинается с вычисления синдромов по схеме Горнера где С; - i-й символ информационного слова;

Ы, - примитивный элемент поля.

После вычисления синдромов So, 9,, $, $ проверяется их равенство нулю, если все S, О, то ошибок нет и блок 3 выдает по шине 15 управляющий сигнал на выдачу информационного слоя во внешнюю систему.. Если все

8; ф О, то возможна одна ошибка и проверяется дополнительное условие

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

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

8 х 8 $

S, õ$ S

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

1429324

S о

С! Зia+C I 1)

Ъ 3

С 1 у ° а @ф где i — место ошибки.

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

С и С вЂ” значения ошибок

У и j — адреса ошибочных символов †примитивн элемент поля Галуа.

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

С = оГ где С вЂ” j-й — элемент по) . . 3 ля; i — степень примитивного элемента.

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

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

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

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

Ф

С вЂ” исправленный символ.

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

20 по принципу один символ в одно слово, следующий во второе и т.д, где С;, — информационный символ, иду щий в первое слово;

С 1 — информационный символ, идущий во второе слово.

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

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

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

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

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

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

iA (i-1)-й (i-2)-й (-3)-й симво- синдром из блоха 7 записывается в

1 пЬь По информационной шине 8 (i-4) "й блок 5. В зависимости от того, равен с ю с мвол поступает в блок 5. Из блока 7 1р он нулю или не равен, по шине 12 шине 17 и 18 поступает С; на вход соответствующая кодовая комбинация

6 Он является адресом, по ко- выдается с выхода блока 5 на вход ока . н явля ит фо ование орому записан результат умножения блока 1, и происходит формир нового адреса управляющих сигналов. о шине 16 поступает в блок 5, где 15 Для проверки равенства, например, фоизводит"я операция сложения по Б х Б .— х Б . = S S u S считываются из

god 2. ?езультат операции поступае". блока 7 соответственно по шинам 17 о шине 1 или о шине ii или 18 и записывается без и 18 и поступают на вход блока 6, и б 7 изменения в лок где они являются адресами таблицы

Управление описанным процессом 2р логарифмов. Из блока 6 считанное из фз блошка 3. Аналогично вычисляются о ычислепия осуществляется управляющи- адресов таблицы логарифмов значение . ающимн по шине 15 степеней примитивного элемента посту- сигналами, поступающими по пает по шинам 8 и 16 о т

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

Ф ь вычисленные символы С;, 8 или 16 поступает на вход блока 6 о вновь в -З и

С, С; являются контрольными как адрес таблицы антило р ф символами информационного слова, Считанное значен ние записывается по

1 оторые поступают из блока 5 по шине шине 17

7 или 18 в блок 7. Аналогично

8 во внешнюю систему. З7 вычисляется S,, Для проверки-равенства полученные значения считываются

В режиме декодирования,по шине 11 из блока 7 в блок 5, где происходит и и сложение по mod 2. В зависимости от поступает уровень логической 1

Выбор начального адреса режима деко- результата операции соответствующий дирования аналогичен режиму кодиро- 5 код пос у ания. По шине 8 в устройство посту- блока 12 и происходит формирование фания. о не пает информационное слово с контроль- нового адр р еса п авляющих сигналов. ными символами, Первый символ без Найденнь др и а ес неисправного символа ий записывается в блок 7. Рас- поступает по шине 17 в блок 4, откуда. изменени эапис

cMovp вычисления синдромов S(„ S<, щ неисправный символ по шине у ое ию 8 пост паS . Б риходом i-го символа. В i, ет в блок 5, где происходит корректис п блоке 7 записаны вычисленные ранее ровка по формуле значения Б, Б, Б, Б . По информа.и I ционной шине 8 i-й символ поступает в блок 5. Из блока 7 по шине 17 или

18 ее значение синдрома пос- где С, — неисправленный символ, поспредыдущ б 4 тупает на вход блока 6, где оно явля- тупивший из блока ется адресом таблицы умножения синд- С; - значение ошибки, поступаюрома на соответствующую const. Вычисения производятся по описанной схеме 5p C; - исправленный c moa.

Горнера, В блоке 5 производится oneа я сложения по шой 2 над пришедшим Операция исправления осуществлясимволом и ранее вычисленным синдро" ется по управ ниц авляницим сигналам постумом, умноженным на со

const поступившим пающим по шине 15 иэ блока 3. Исправпо шине из лока . ез

16 б 6 P ультат вы- ленный символ по шине 8 записывается

55 числения записывается в ло

ыв ется в блок 7 Зна- иэ блока 5 в блок 4. После исправле- чение операми- лока щи- блока 5 выбор таб- ния всех ошибок слово из блока 4 лиц в блоке 6, выбор адресов в блоке выдается по шине 8 во внешнюю сис7, направление передачи определяются тему.

Составитель С. Берестевич

Редактор О. Головач Техред Л. Олийнык Корректор С. Черни

Заказ 5144/5á, Тираж 929 Подписное

ВНК1ПИ Государственного комитета СССР .по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

7 142

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

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

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

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

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

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