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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано при создании устройства , исправляющих ошибки в хранимой или передаваемой по каналам связи информации . Целью изобретения является повьтение быстродействия устройства. Устройство содержит запоминающий блок 1, буферный накопитель 2, блок 3 сумматоров по модулю два, генератор 4 синдромов, накопитель 5 синдромов , вычислитель 6 злементарных симметрических функций, Дешифратор 8 ошибок и блок 7 вычисления ошибок, состоящий из злемента И 9, счетчика 10 импульсов, четырех регистров 14- 17, восьми блоков 11-13, 21,26-29 постоянной памяти, шести коммутаторов 18-20, 30-32, перемножителя 22, двух групп 23 и 33 из га триггеров и двух блоков 24 и 25 оперативной памяти. Введение пяти блоков постоянной памяти , группы из m триггеров и трех коммутаторов позволяет реализовать одновременное определение корней канонического квадратного уравнения локаторов , величины, используемой в последующем для вычисления значений ошибок , и сокращает количество тактов исправления двухкратных ошибок в 1,5 раза, где m - размерность поля GF (2) Галуа. 2 табл.,1 ил. а. Од N5 00

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

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

РЕСПУБЛИК

Ц9) Ш) ся) 4 H 03 M 13/02

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

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

K ABTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 42?0966/24-24 (22) 01 . 04. 87 (46) 23.10.88.Бюл.Р 39 (7 2) В.H.ßùåíêo (53) 681.325.63 (088,8)

{56) Питерсон У., Уэлдон 3. Коды, исправляющие ошибки. — М.: Мир, 1976, с.203,204, 207, фиг.7.11, 7.14.

Авторское свидетельство СССР

11 913383, кл. G 06 F 11/08, 1978.

Авторское свидетельство СССР

h» 1216832, кл. Н 03 М 13/00, 1986. (54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ

ОШИБОК (57) Изобретение относится к вычислительной технике и может быть использовано при создании устройства, исправляющих ошибки в хранимой или передаваемой по каналам связи информации. Целью изобретения является повышение быстродействия устройства,, Устройство содержит запоминающий блок 1, буферный накопитель 2, блок

3 сумматоров по модулю два, генератор 4 синдромов, накопитель 5 синдромов, вычислитель б элементарных симметрических функций, дешифратор 8 ошибок и блок 7 вычисления ошибок, состоящий из элемента И 9, счетчика

10 импульсов, четырех регистров 1417, восьми блоков 11-13, 21,26-29 постоянной памяти, шести коммутаторов

18-20, 30-32, перемножителя 22, двух групп 23 и 33 из m триггеров и двух блоков 24 и 25 оперативной памяти, Введение пяти блоков постоянной памяти, группы из m триггеров и трех коммутаторов позволяет реализовать одновременное определение корней канонического квадратного уравнения локаторов, величины, используемой в последующем для вычисления значений ошибок, и сокращает количество тактов исправления двухкратных ошибок в

1,5 раза, где m — размерность поля

GF (2 ) Галуа. 2 табл.,1 ил.

1432787

Изобретение относится к вычислительной технике, и может быть использовано при создании устройств, корректирующих ошибки, возникающие в информационных посылках при их хранении или передаче по каналам связи и предназначено для работы с м кодами Гида-Соломона длины n - -2 -1, в каждой кодовой комбинации которого имеется К информационных и и-К проверочных символов, каждый иэ которых содержит m двоичных разрядов, где м

m — размерность поля GF (2 ) Галуа.

Образующий полином кода для исправления двухкратных ошибок 9(х)

=(х+1) (х4-сЦ (х+ м ) (х+ Ы ), где оС примитивный элемент поля GF (2 ) Га-. м луа е

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

На чертеже представлена функциональная схема устройства

Устройство содержит запоминающий блок 1, буферный накопитель 2, блок 25

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

Ьлок 7 вычисления ошибок состоит из элемента И 9, счетчика !О импульсов, блоков 11-13 постоянной памяти, регистров 14-17, коммутаторов !8-20, блока 21 постоянной памяти, перемно35 жителя 22, группы 23 из m триггеров, блоков 24 и 25 оперативной памяти, блоков 26-29 постоянной памяти, коммутаторов 30-32 и группы 33 иэ m триггеров. 40

Устройство работает следующим образом.

В запоминающем блоке I с помощью образующего полинома.9(х) записывается закодированная избыточным (п,К) 4> кодом Рида-Соломона кодовая комбинация С(х). При передаче по каналу связи или при считывании с блока 1 на

G(x) накладывается вектор ошибок (x), в результате чего в буферный накопитель 2 и генератор 4 синдромов поступает в последовательность R(x)

=G(x) + Е(х).

В генераторе 4 деления R(x) на составные части образующего полинома

9(х) =(х+1) (х+м) (х+ ol, ) (х+М ) получа" ют синдромы S,S,,S,S которые за" писывают в накопитель 5 синдромов.

На выход накопителя 5 подключен деS<+ G

$2+ С,$<= О!

Sú+ G<$2 О!

2 $« С2$ 0<

S + С,Б,+ С,Б,= О. э

Последовательность работы вычисли" теля 6 следующая, Если $ А О, то 1 ь 1 и определяют

С,= Б„/Б; Б + С<8< и Б, С,$2 ° Если

$2+ G S S9+ G $2- О, то 1 — 1 х Х<—

G<, Y< = S

1 2 и вычисляют .

S, + Б Б; G„= ($$ + S sq)/Ы (S< Sú $ ã,) /

S + G<$2+ G2$ < °

1 I

Если D Ф О.или если S,= S, = 0 и

S Ф О, то 1) 2 и принятая кодовая комбинация стирается. Если D = О, то 1 = 2 по сигналу с вычислителя 6 в блоке 7 производят определение ошибок.

I ..Последовательность работы блока

7 следующая.

Локаторы ошибок находят из квадратного уравнения канонического вида

z+ z+(= О, (4) 2 где II = С /С,;

z - =X/G шиФратор 8, Функционирую<пий как элемент ИЛИ. Если S = S< = $ "- Б,то на втором выходе дешифратора 8 появляется сигнал "Нет ошибки" и кодовый блок выдается потребителю путем подачи сигнала "Считывание" на управляющий вход буферного накопителя 2, В противном случае получают остаток от деления, содержащий хотя бы одну

1,, тогда на выходе дешифратора 8 появляется сигнал "Ошибка", который дает разрешение для работы вычислителя 6.

В вычислителе 6 определяют кратность 1 ошибки и значения С<и G< элементарных симметрических функций из соотношений

1432787 откуда (5) Х,= г<С,;

Х z G(где г„ и z< — решение уравнения (4).

Так как уравнение (4) имеет ненулевые корни только при определенных значениях f, то операцию решения 10 (4) просто реализуют табличным способом с помощью блоков 27 и 28 постоянной памяти. Для всех возможных значений, при.которых !(4j имеет ненулевые решения, заранее определены величины z„ и z и по каждому адресу $ в блок 27 занесены соответствующая величина z, а в блок 28—

z<. При подаче на адресные входы бло-. ков 27 и 28 величины 11 с их выходов 20 считывают соответствующие величины г и г °

После определения локаторов Х< и Х из (5) производят определение значений У и Y ошибок из соотношений (3), которые для кода РидаСоломона с порождающим многочленом

9(х) = (х+1) (х+<с) (х+1 ) (x+of ) имеет вид

30 о о

У<Х + У Х = Б .; (6) УХ, +YХ =S является адресом для блока 29, на входе которого появляется записанная по этому адресу величина 1/С,. Блок

21 памяти подключает с помощью коммутатора 20 выходы блока 29 на вход блока 13 памяти. Значение 1/G, явля— ется адресом для блока 13. В результате на выходе блока 13 появляется записанная в нем по этому адресу величина 1/G,. Таким образом, на первых, г входах перемножителя 22 появляется величина С,а на вторых — 1/G,. Од1 новременно блок 21 памяти подключает через коммутатор 30 выход перемножителя 22 на входы блоков 27 и 28 памяти. На этом же такте происходит умножение С и 1/G< и с выхода перемножителя 22 полученная величина f через коммутатор 30 подается на блоки

27 и 28. Величина является адресом для блоков 27 и 28, по которому в них записаны соответственно z u z . В результате на выходе блока 27 йоявляется величина г< „ которую записывают в блок 23 группы иэ т триггеров, а на выходе блока 28 — zz, которую записывают в блок 33 и m триггеров.

На втором такте с выходов блока

11 на блоки 24 я 25 оперативной памяти подаются сигналы записи и выдает" ся адрес, по которому величина г, saписывается в блок 24, à z — в блок

25.

На третьем такте блок 12 с по35 откуда

s + ях, у = — — — —-x,+ х, 40

Блок 7 при 1 = 2 работает следующим образом.

При обнаружении ошибок из блока 6 45 .в блок 7 выдается сигнал, который открывает элемент И 9. Через него начинают поступать тактовые импульсы

Т на счетчик 10. На выходы счетчика

10 подключены блоки 11,12,21 и 26 постоянной памяти.

На первом такте блок 12 подключает с помощью коммутатора 18 на входы перемножителя 22 выходы регистра 16, а выходы регистра 17 через блок 29 памяти, коммутатор 20 и блок 13 памяти с помощью коммутатора 19 на вторую шину перемножителя 22. Значение G, записанное в регистре 17, мощью коммутатора 18 подключает на первые входы перемножителя 22 выходы блока,.24, блок 11 выбирает из блока 24 величину г,, которая подается на входы перемножителя 22. Одновременно блок 12 с помощью коммутатора 1.9 подключает выход регистра

17 на вторые входы перемножителя 22, а блок 26 с помощью коммутаторов 31 и 32 подключает выход перемножителя

22 на входы групп 23 и 33 триггеров.

Таким образом, на выходе перемножителя 22 получен локатор ошибок Х, .г,С,, который записывается в триггеры групп 23 и 33.

На четвертом такте локатор Х, с помощью блока ll с группы 23 тригге. ров переписывается в блок 24.

На пятом такте блок 11 выбирает из блока 25 величину z которая с блоком 12 через коммутатор 19 подается на входы перемножителя 22. На входы перемножителя блоком 12 с помощью коммутатора 25 подается вели1432787

Таблица!

Двоичный вид символа GF(2 ) 50

0 0 0

0 0 l

0 1. 0

1 0 0

0 l 1

1 = С

5 чина G< с блока 17. Блок 26 с помощью коммутаторов 31 и 32 подключа6т выходы перемножителя 22 на входы, групп 23 и 33 триггеров. В результате в группу 23 триггеров записывается локатор Х С г .В группе 33 триггеров локатор Х складывается по мой

Дулю два с локатором Х, который бып

Записан на третьем такте.

На шестом такте с помощью блока

Il локатор Х с группы 23 триггеров переписывается в блок 24, а (Х,+ Х ) с группы 33 триггеров в блок 25.

На седьмом такте блок 26 с помощью коммутатора 31 подключает выходы регистра 15 на входы группы 23 триггеров, в которую записывается S<

На восьмом такте блок ll выбирает иэ блока 24 локатор ошибок Х . Блок

12 с помощью коммутатора 18 йодает на первые входы перемножителя 22 локатор Х, а с помощью коммутатора

19 на вторые входы перемножителя

22 " синдром $ . Блок 26 с помощью коммутатора 31 подключает выходы перемножителя 22 на входы группы 23 триггеров. В результате на выходе перемножителя 22 получают величину

$ Х, которая складывается по модудва с синдромом S, записанным в триггерах 23 группы.

На девятом такте полученная величйна $ОХ + $, переписывается в блок

24, На десятом Факте блок 12 с помощью коммутатора 18 подключает выходы блока 24 на первые входы перемйожителя 22, а с помощью коммутатора 19 — выходы блока 13 на вторые вХоды перемножителя 22. Одновременно блок 21 с помощью блока 20 коммутирует, подключает выходы блока 25 на вХоды блока 13, блок 26 с помощью коммутатора 32 — выходы перемножителя 22 на входы группы 33 триггеров.

Блок Il выбирает из блока 24 величину $ Х + $,, которая поступает на первые: входы перемножителя 22, а из блока 25 — величину Х, + Х, являющуюся адресом для блока 13, по которому записана величина 1/(Х,+ Х ), поступающая на вторые входы перемножителя 22. Следовательно, на выходе перемножителя получают значение ошибS Х 4 $4 ки У - - — — -, которое эаписыва4 Х,,+Х ется в группу ЗЗ триггеров.

На одиннадцатом такте величина

У, с помощью блока ll переписывается в блок 25.

На двенадцатом такте блок 26 с помощью коммутатора 32 подключает выходы регистра.14 на входы группы .33 триггеров, в которую записывается величина So . Одновременно локатор

Х, являющийся адресом искаженного элемента, подается на буферный накопитель 2, в результате разряды искаженного символа с адресом Х подаются на блок 3 сумматоров по модулю два1 на вторые входы которых подается ошибка с помощью блока ll, При сложении разрядов искаженного символа с У, происходит исправление и исправленный элемент вновь записывается в буферный накопитель 2 по тому же адресу.

На тринадцатом также, аналогично как и иа десятом такте, на входы группы триггеров ЗЗ подают величину

25 У, которая складывается по модулю два с величиной $О, записанной на две. надцатом такте.

Полученная в результате величина

У У + $4 на четырнадцатом такте

3О переписывается в блок 25.

На пятнадцатом такте производят исправление искаженного символа с номером Х аналогично тому, как это делают на двенадцатом такте.

Рассмотрим процесс исправления двухкратных ошибок на конкретном примере для кода Рида-Соломона длины

7 с образующим полиномом 9(x) = (х+

+I) (х+о ) (х +оР) (х + о ) длиной 7, в

4п котором имеют 3 информационных и 5 проверочных, символов поля GF(2 ), Ъ каждый из которых содержит 3 двоичных разряда в соответствии с табл.1.

Символ поля GF(2 ) 1432787

Продолжение табл.1

В 2 4 2

8о8ь о + +

1 l 0

1 1 1

1 0 l

5 поступают на входы соответственно регистра 16 и регистра 17. Из блока

6 в блок 7 выдается сигнал, открывающий элемент И 9 и через него поступают тактовые импульсы на счетчик

10, выходы которого подключены к адресным входам блоков ll 12,21 и 26 постоянной памяти.

Допустим при передаче по каналу связи слова кода Рида-Соломона

001 eL о6 Ы на позициях с номерами и ф = 1 проиэошли ошибки и в буферный накопитель 2 поступает слово 5 6 4

С выходов блока 5 синдромы S

Я о

S K K" з дают на входы блока 6. Кроме того, S и S записывают соответственно в регистры 14 и 15. С выходов блока 6 величины

15 На первом такте с выхода перемноGz o жителя 22 = --- = ---- oL в двоо

I ичном виде 010 поступает на адресные

20 входы A А» А блоков 27 и 28 посо тоянной памяти, в которых по адресу для всех возможных значений А занесены соответствующие им значения Do, D,, D корней уравнения (4) z, (в блоке 27) и z (в блоке 28) в соответствии с табл.2.

Таблица2

Выход данных блока 27

Двочи

Значение г в поле GF(2 ) вид z

ДВОИЧНЫЙ ВИД ный Значение

I z в поле

GF(2 ) а

Значение в поле

GF(2 ) Двоичный вид о »

А )А, А

ot. 1 0 1

0 l 0

1 0 0

1 1 0

l 0 0

1 1 0 5 ! оА 0 1 0

0 1 0 виде 010 записывают в триггеры групп

23 и 33.

На четвертом такте величину Х переписывают в блок 24.

На пятом такте с выходов перемножителя 22 локатор Х = z G и o», - =1

6 в двоичном виде 001 записывают в группы 23 и 33 триггеров, причем в группе 33 триггеров х4 и х суммиРуются по модулю два

На шестом такте локаторов Х в двоичном виде 001 записывают в блок

24, а сумму (Х,+ Х ) в двоичном виде 010 — в блок 25.

По адресу Ао А» А 010 в блоке 27 занесены двоичная последовательность

РоР D — 100, что соответствует г

= о, в блоке 28 — 1 01, что соответствует z = оС . Величина z» и z в

6 двоичном виде записывают соответственно в блок 23 и блок 33 группы из

3 триггеров.

На втором такте величину z» (1 00) записывают в блок 24, а г (101) в блок 25.

На третьем такте с выхода перемножителя 22 полученный локатор ошибок

Х = 2 G 1 о . 0L = OL .В ДВОИЧНОМ

Адресные входы блоков

27, 28

S» Sç+ Sz о 1 +о»м

Выход данных блока 28

9 1432787

На седьмом такте в группу триггеров 23 записывают $< в двоичном виде

ill . что соответствует значению aL которую на восьмом такте в группе 23 суммируют по модулю два с двоичной, последовательностью — 110, соответствующей величине S Х 2 1

Ф поступающей,с выхода перемножителя ф )

22. Полученную сумму $ Х + $, и " +

+ М в двоичном ниде 001 переписывают в блок 24 °

На десятом такте с выходов перемножителя значение ошибки

$ Х + $ 1 у а

X,+ Х оС в двоичном виде 101 записывают в группу 33 триггеров, которую на одиннадцатом такте переписывают в блок 25.

На двенадцатом такте в блоке 3 сумматоров по модулю два проводят сло.жение искаженного символа с номером . о с Y Ы б и исправленный элемент

1 25 символ имеет значение 1 + Ы = М, Тринадцатый такт аналогичен деся тому. При этом в группе 33.триггеров ,величина Y„= g суммируется с величиной $ = Ы,записанной на двенад4

;цатом такте. Полученное значение

Y + S =о б + K4 о 3 на четыр о надцатом такте переписывают в блок 25, На пятнадцатом такте, как и на две,надцатом, производят исправление симо вола с номером Хо = о = 1 и исправленный символ имеет значение о + К == 0L °

Таким образом, после исправления в буферном накопителе 2 занесено

"очищенное" от двух ошибок слово

001 а Ы М Ы

При возникновении однократных ошибок счетчик 10 устанавливается сигналом "Установка" с второго управляющего входа блока 6 в 16-е состоя45

we, В этом состоянии блок 26 с помощью коммутатора 31 коммутирует вы" ходы регистра 17 на входы группы 23 триггеров, в которые записывается величина X = G,, а с помощью коммутатора 32 — выходы регистра 14 на входы группы 33 триггеров, в которую записывается величина Y,= $„, На семнадцатом такте производят запись величины Х, -в блок 24, а вею!ичины 7 — в блок 25, Исправление однократной ошибки осуществляют так же, как и двухкратных.

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

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

m — - размерность поля QF(2 ) Галуа, выходы которого подключены к вторым входам буферного накопителя и являются информационными выходами устройства, выходы генератора синдромов подключены к входам накопителя синдромов, первые, вторые, третьи и четвертые выходы которого соединены с соответствующими входами вычислителя элементарных симметрических функ-. ций и входами дешифратора ошибки, первый выход которого подключен к пятому входу вычисли-еля элементарных симметрических функций, второй выход соединен с третьим входом буферного накопителя и является контрольным выходом устройства, блок вычисления ошибок, включающий элемент

И, счетчик импульсов, первый — третий коммутаторы, первый — третий блоки постоянной памяти, перемножитель, первую группу из m триггеров, первый и второй блоки оперативной памяти и первый, второй, третий и четвертый регистры, выход элемента И подключен к счетному входу счетчика импульсов, выход которого соединен с входами первого и второго блоков постоянной памяти, выход первого регистра подключен к первому входу второго коммутатора, выходы второго ( и .третьего регистров подключены соответственно к первому и второму входам первого коммутатора, выход четвертого регистра подключен к третьему входу первого коммутатора и второму входу второго коммутатора, выходы третьего коммутатора подключены к входам третьего блока постоянной памяти, выход которого соединен с третьим входом второго коммутатора, первый и второй выходы второго блока постоянной памяти подключены к четвертым входам соответственно первого и второго коммутаторов, выходы которых соединены с соответствующими входами перемножителя, первый и второй .выходы первого блока постоянной памяти подключены к первым вхоСоставитель О.Тюрина

Редактор Г.Волкова Техред И.Берес Корректор Н.Король

Заказ 5464/SS Тираж 929 Подписное

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

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

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

ll 1432

Дам соиTBeTCTBPHHO llEpBOI 0 H BTOpOI O блоков оперативной памяти, выходы первой группы из ш триггеров подключены к вторым входам первого блока оперативной памяти, выходы которого подключены к пятым входам первого коммутатора и четвертым входам буферного накопителя, выходы второго блока оперативной памяти соединены с первыми входами третьего коммутатора и вторыми входами блока из m сумматоров по модулю два,- первый вход элемента И и установочный вход счетчика импульсов подключены соответственно к первому и второму управляющим выходам вычислителя элементарных симметрических функций, входы первого-четвертого регистров подключены соответственно к первому и второму выходам накопителя синдромов и первому и второму информационным выходам вычислителя элементарных симметрических функций, второй вход элемента И является тактовым входом уст- 25 ройства, отличающееся тем, что, с целью повышения быстродействия, в блок вычисления ошибок введены четвертый — восьмой блоки .постоянной памяти, четвертый — шестой комму- чц таторы и вторая группа из m триггеров, выходы которой подключены к

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