Устройство для исправления ошибок
Изобретение относится к вычислительной технике и может быть использовано при создании устройства , исправляющих ошибки в хранимой или передаваемой по каналам связи информации . Целью изобретения является повьтение быстродействия устройства. Устройство содержит запоминающий блок 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 вторым входам второго блока оперативной памяти, выходы четвертого и пятого блоков постоянной памяти объединены и подключены к выходу счетчика импульсов, первый и второй выходы четвертого блока постоянной памяти подключены соответственно к первому входу четвертого коммутатора и второму входу третьего коммутатора, третий вход которого соединен с выходом пятого блока постоянной памяти, вход которого объединен с первым входом пятого коммутатора и подключен к выходу четвертого регистра, первый вход шестого коммутатора. соединен с выходом первого регистра, выходы перемножителя подключены к вторым входам четвертого — шестого коммутаторов, первый н второй выходы шестого блока постоянной памяти подключены к третьим входам соответственно шестого коммутатора и пятого коммутатора, четвертый вход которого соединен с выходом второго регистра, выход четвертого коммутатора подключен к входам седьмого и восьмого блоков постоянной памяти, выходы которых объединены соответственно с выходами пятого и шестого коммутаторов н подключены к входам первой и второй групп из триггеров.
