Устройство для вычисления синдромов кода рида-соломона

 

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

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

СОЦИАЛИСТИЧЕСНИX

РЕСРУБЛИН (l9) (И) ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 447589 1/24-24 (22) 23.08.88 (46) 15.06.90. Бюл. ¹ 22 (71) Курский политехнический институт (72) В.В.Гвоздев, А.П.Типикин и С.И.Егоров (53) 68 1.3?6 (088.8) (5á) Блох Э.Л., Эяблов В.В. Обобщенные каскадные коды. М.: Связь, 1976, с. 112, рис. 3 43.

Техника средств связи. Серия: техника радиовещательного приема и акустики, 1984, Р 3, с. 77, рис. 3 (прототип). (51)5 Н 03 И 13/00 13/02

2 (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИНДРОМОВ КОДА РИДА-СОЛОМОНА (57) Изобретение относится к вычисли-, тельной технике. Его использование в системах хранения и обработки цифровой информации позволяет повысить достоверность работы устройства за счеT аппаратного контроля правильности его функционирования. Устройство содержит буферные регистры 1, блоки

2 сумматоров по модулю два и группу

3 преобразователей кода. Поставленная цель достигается благодаря введению соединителей 5, групп 4, 6 блоков свертки по модулю два, сумматоров 7-9 по модулю два и триггеров

10, 11. 3 ил. (1t I) ,В R, (ittl й

=;В(А + R(С1. ) (2) ° Э ° (1+1)

X К„ (it 1)

k (1+1)

-X

i (1+1j

+ЯК,"

gQR;

1=1

+ ° ° °

; R(i+t) (3) 45

)«1 г 5=, (4)

Если число К контрольных разрядов четное, то первый член в правой части формулы (4) отсутствует. Для этого случая формула (4) имеет следующий вид () !

+ R . д(" (1а 11

К- I (i) (1) i« K- é .

Изобретение относится к вычисли тельной технике и может быть использовано в системах хранения и обработки цифровой информации.

Цель изобретения — повышение достоверности работы устройства за счет аппаратного контроля правильности, его функционирования.

На фиг. 1 изображена функциональная схема устройства; на фиг. 2 и 3— выполнение соответственно преобразователей кода и соединителей. (Устройство содержит буферные реГистры 1 числом к (к — числО конт рольных символов в коде Рида-Соломона), К блоков 2 сумматоров по модулю два, К преобразователей 3 кода, первую группу 4 блоков свертки по модулю два, К соединителей 5, вторую группу

6 блоков свертки по модулю два, rtepвый-третий сумматоры 7-9 по модулю два, первый и второй триггеры 10 и

11. На фиг. 1 обозначены информацион" ные входы 12, тактовый вход 13, пер- 25 вый и второй установочные входы 14, 15, первые К-тые выходы 1б, (К+1)-й выход 17.

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

Устройство для вычисления синдромов

35 построено по схеме вычисления значений полиноыа полученного слова в корнях порождающего многочлена. Содержимое регистров 1 ° .1 1 1 ° 2 1 ° о °

1.К-1, 1.К в i-м, такте обозначают, (il (1) () (i) 4

-соответственно R К, ... R„, К„., Определяют содержимое регистров 1.1, 1.К-1, 1.К в (i+1)-м такте, зная алгебраические правила функционирования схемы вычисления синдромов, как следующее,c4 "t, Ы " к " — значения корней порождающего многочлена кодов РидаСаломона (г б (О, 1, 2, ..., 2 — 2 ) g(x) = (х + (") (х + Ы "" ), ... ° .«(х+ М )(x+oc ), которые являются элементами конечного поля Галуа GP(2 ) характеристики

Ь два.

Используя систему формул (1), определяют свертку по модулю два содержимогб регистров 1.1, 1.2, 1.К-1, 1.К в (i+1)-м такте (K — условное обозначение свертки по модулю два- значений двоичных разрядов элементов поля) Четность содержимого всех регистров 1.1, 1.2, ..., 1.К- 1, 1.K определяется по следующей формуле где .7., †. обозначение операции суммирования по модулю два. (1)

Подставляя в (3) вместо R >. их

r выражения из системы формул (2) и раскрывая скобки, получают

А К с( (+1) к где А — символ на информационных ()

r 111 входах 12 в i-м такте; К, g(1=! =1

Если число K контрольных разрядов нечетное, то формула (4) имеет вид

5 1571773 к

+, а " ." ) (6) ) к

-„г р Нс + > = Ас )

1 где

Перед началом работы устройства первый и второй триггеры 10 и 11 по сигналу, поступающему на установочный вход 15, устанавливаются в нулевое состояние. Каждый цикл работы состоит из и тактов, где п — длина кодового слова в символах. В начале АО первого такта каждого цикла с выхо° дов 16.1 - 16.К снимаются вычисленные в предыдущем цикле синдромы предыдущего слова. Затем в этом же такте содержимое регистров 1.1 — 1.К по сиг- 5 налу, поступающему на установочный вход 14, устанавливается в нулевое состояние. По окончании первого такта поступающий на информационные входы 12 первый символ следующего слова по тактовому сигналу, поступающему на тактовый вход 13, запоминается в регистрах 1.1 — 1,К. В каждом из остальных п-1 тактов цикла .на информационные входы 12 поступает очередной символ слова и выполняется очередной этап вычисления значений полинома полученного слоя в корнях порождающего многочлена.

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

1.1 — 1.К в общем случае

1

,=, ), = f(R) +A + (к g" ) 10

1 (7) О, если К вЂ” четное

f (r.) 1, если К вЂ” нечетное.

Блок 6.(К+1) свертки по модулю два реализует,Ь Л, соединители

5:.1 — 5.К и соответствующие блоки

6.1 — 6.К свертки по модулю два реализуют соответственно, ь (ск,, g " )— — Я (К к ° ск, ), первый сумматор 7 реализует ХА +,>,3(К с() . !

Блоки 4.1 — 4.К свертки по модулю два реализуют соответственно R, — Q R „, второй сумматор 8 реали(>+i) к с + i) зует о Q R

J (°

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

В i-м (i = 1,n) такте работы устойства на информационные входы 12 поступает очередной символ Ас 1 . С помощью первого — К-ro преобразователей 3.1 -З.К кода и первого — К-го блоков 2.1 — 2.К сумматоров по модулю два выполняется очередной этап вычисления значений полинома поступающего слова в корнях порождающего многочлена g(X) . Преобразователи

3.1 — З.К кода реализуют процедуру умножения содержимого соответствующих регистров 1.1 — 1.К соответственно на ск " — ск " . На информационных входах регистров 1.1 — 1.К формируется информация о следующем состоянии этих регистров, исходя из формулы (1). С помощью соединителей 5.1 — 5.К и блоков 6.1 — 6.(К+1) свертки по модулю два на выходе первого сумматора

7 формируется сигнал четности следующего состояния содержимого регистров 1.1 — 1.К согласно правой части формулы (7). По окончании i-ro такта по тактовому сигналу, поступающему на тактовый вход 13, сигнал четности с выхода первого сумматора 7 запоминается в первом триггере 10:, а информация с выходов блоков 2.1 — 2.К переписывается в регистры 1.1 — 1.К.

В следующем (i+1) ì такте с помощью блоков 4.1 — 4.К свертки по модулю два на выходе второго сумматора 8 формируется сигнал четности содержимого регистров 1.1 — 1.К согласно левой части формулы (7). Сформированный с помоцью этих блоков сигнал четности сравнивается путем суммирования по модулю два в третьем сумматоре 9 с ранее сформированным в х-м такте сигналом четности, хранящимся в первом триггере 10. Если данные два сигнала четности различны, то на выходе третьего сумматора 9 формируется сигнал сбоя, который по окончании (i+1)-ro такта по тактовому сигналу, поступающему на тактовый вход

13, запоминается во втором триггере

i1. Одновременно в (i+1) ì такте формируется с помощью соединителей 5.1

5.К, бгоков 6.1 — 6.(К+1) свертки по модулю два и первого сумматора 7 сигнал четности следующего состояния регистров !.1-1.К, который по такто1 вому сигналу, поступающему на вход

13, запоминается в первом триггере

10. На информационных входах регист,ров 1.1 — 1.К формируется информация

1571773

О следующем состоянии этих регистров аналогично, как в i-м такте, и так далее. Сигнал сбоя, если сбой имеет м!есто, с выхода второго триггера 11 о 5 передается на (К+1)-й выход 17 устройства.

Пример для случая К = 4 конечного

Поля Галуа GF(2 ), .образованного не-!

1риводимым многочленом Х + Х + 1, Ф порождающего многочлена g(X) (Х + )(К + й)(К + 3)(К + 4) ормула (7) для этого случая имеет ледующий вид

l к . KXR" =XX(R, - cC ).

5=! 3°, j=i

Для этого преобразователи 3. 1 - 3.Ê

° ° ° ° ода выполнены на элементах 18 ИСКЛЮЧ!ЕЕ ИЛИ (фиг. 2), что обеспечивает ножение на, о, С, О!, в поле

Р(2 ) . Соединители 5. 1 — 5.4 предф тавляют собой фиктивные блоки — это есткие проводниковые соединения . фиг. 3). Построение такого соедини- 25 теля например, третьего 5.3, следующее. Обозначают информацию, поступаюРю в i-м такте на вход блока 5.3, которая является содержимым третьего егистра 1.3 и может быть представле- 30 на в виде элемента конечного поля

Галуа СР(2"), следующим вектором а3

az.()

R3 ао

Э о аэ + аа

+ а! (8) а, 50

Определяют свертку по модулю два выражения (8), + аа) + (а2 + а1) + а4а i! °

Выполняя умножение в конечном 40 .йоле Галуа GF(2 ) вектора R на

Э 3

Постоянный коэффициент ф, получают

Следующее выражение

Таким образом, для конкретного примера (фиг ° 3) лишь четвертая линия а!! из общего числа четырех линий входа блока 5.3 соединена с выходом этого же блока 5.3. Аналогичным об,разом определяется схема соединений для остальных соединителей 5.

Предлагаемое изобретение позволяет повысить достоверность работы устройства для вычисления синдромов кода Рида-Соломона за счет проверки в каждом такте правильности функционирования путем предсказания по четности следуюшего состояния содержимого регистров этого устройства.

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

Устройство для вычисления синдромов кода Рида-Соломона, содержащее первый — К-й блоки сумматоров по модулю два (К вЂ” число контрольных символов в коде Рида-Соломона), выходы которых соединены с информа!:-!онными входами одноименных буферных регистров, установочные и тактовые входы которых соответственно объединены и являются соответственно первым установочным и тактовым входами устройства, выходы первого — К-го буферных регистров подключены к входам одноименных преобразователей кода и являются соответственно первыми — К-ми выходами устройства, выходы первого—

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

Функционирования, в устройство введены соединители, первая и вторая группы блоков свертки по модулю два, первый — третий сумматоры по модулю два и первый и второй триггеры, установочные входы которых объединены и являются вторым установочным входом устройства, входы одноименных соединителей и блоков свертки по модулю два первой группы соответственно объединены и подключены к выходам одноименных буферных регистров, выходы первого — К-ro соединителей соединены с входами одноименных блоков свертки по модулю два второй группы, 9 15 входы (К+1)-ro блока свертки по модулю два второй группы подключ ены к соответствующим информационным входам устройства, выходы всех блоков свертки по моцулю два второй и первой групп соединены с входами соответственно первого и второго сумматоров по модулю два, вьглоды которых соединены соответственно с информационным входом первогб триггера и пер71773 вым входом третьего сумматора по модулю два, тактЬвые входы триггеров объединены и подключены к тактовому входу устройства, выход первого триггера соединен с вторым входом третьего сумматора по модулю два, выход которого подключен к информационному входу второго триггера, выход которого является (К+1)-м выходом устройства.

1571? 73

Составитель О.Ревинский

Техред Л.Сердюкова Корректор С.Шекмар

Редактор И.Касарда

Заказ 1522 Тираж 662 Подписное

BfllHKIH Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101