Устройство для кодирования циклических кодов Советский патент 1990 года по МПК H03M13/15 H03M13/51 

Фиг.1

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

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

На фигс 1 изображена функциональ- ная схема устройства; на фиг. 2 и 3 - примеры выполнения соответственно преобразователей кода и соединителя.

Устройство содержит буферные регистры 1 числом К (К - количество контрольных символов в кодовом слове циклического кода), К блоков 2 сумматоров по модулю два, К преобразователей 3 кода, первый и второй блоки 4 и и 5, элементов И, К + 2 блоков 6 свертки по модулю два, соединитель 7, первый - третий сумматоры 8-10 по модулю два и первый и второй триггеры 11 и 12. На фиг. 1 обозначены информационные входы 13, первый и второй управляющие входы 14 и 15, тактовый вход 16, установочный вход 17, первый и второй выходы 18 и 19.

Принцип аппаратного контроля устройства для кодирования (кодера) ос- чован на методе предсказания следующего состояния содержимого регистров 1.1 - 1.К по четности (по модулю два) зная алгебраические правила функционирования кодера. Кодер циклического кода (фиг. 1) построен по схеме деления на порождающий многочлен g(x). Содержимое регистров 1.1, 1.2,..., К (К-1), 1.К в i-м такте обозначим соответственно R , , R ,. .. RK(.,i R J Определим содержимое регистров 1.1, 1.2,., .,1 . (К-1), 1.К в (i-H)-M такте, зная алгебраические правила функционирования кодера, как следующее:

(1)

А - символ на информационном входе 1 3 в i-м такте; gSK-I-SK коэффициенты соот

ветственно при

,х,

VK .л .А

к-t,

в порождающем многочлене

к-1.

5

+ gk.(x 4 -4 gzx( 81

циклического кода, которые являются элементами конечного поля Галуа GFCg1),

Используя систему формул (1),определим свертку по модулю два содержимого регистров 1.1, 1.2,...,1.(К-1), 1оК в (i-H)-M такте ( - условное обозначение свертки по модулю два значений двоичных разрядов элемента поля) :

„(

ZR, - 5 ( R( .g,)

lR(r

Ј(R(; +

8«

(2)

IV С

,+ Л в„.

Четность содержимого всех регистров 1.1, 1.2,.,.,.(К-1), 1.К определяется по следующей формуле:

...+

+ жО IERC:, о)

где 51- обозначение суммирования по

модулю два.

()

Подставляя в (3) вместо RJ их выражения из системы формул (2), раскрывая скобки и изменяя порядок суммирования в последнем члене, получим

I5R( gsR /

. -. /T,U) к

g (R Поразрядную сумму

8j.

(4)

g . можно

J«

представить соответствующим элеменIC

том g X 8 конечного поля Галуа

j--

GF(gm). Таким образом, четность со- держимого регистров 1.1,1.2,,.„,1.(К- 1), 1.К в (1-И)-м такте будет определяться по следующей формуле: к ,-.., ,., ни

iR(r ЖАЫ+ gmR;«.

+(R. g). (5;

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

Ы

реализует Ж А , блоки 6.1-6.(К-1)

«I

ДО

реализуют соответственно R - Rk, в i-м такте, соединитель 7 и блок 6.(К+2) реализуют 3(R gp), первый сумматор 8 реализует Ж

к-( ,.,

+ ;«i j

ЈА

gp). Блоки 6.1 - 6.К свертки по модулю два реализуют

Г

соответственно

(i+D-н

такте, второй сумматор 9 реализует

isR r1.

J-1

J

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

)-U+/ () . . . ) (

где cCV...i

е( r oi r+K-t элементы конечного поля Галуа GF(2) хзэактеристики два

(reft),1,2,....2b-2j

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

Перед началом работы кодера первый и второй триггеры 11 и 12 по сигналу, поступающему на установочный вход 17, устанавливаются в нулевое состояние.

Каждый цикл работы кодера состоит из п тактов, где п - длина кодового кода в символах. Первые n-К тактов цикла первый блок 4 элементов И согласно сигналу, поступающему на первый управляющий вход 14, открыт, и информационные символы А1 1} (, n-К) кодового слова, поступающие на информационные входы 13, проходят через первый блок 4 элементов И

В последующих К тактах цикла первый блок 4 элементов И закрыт (отсутствует сигнал на первом управляющем входе 14). Первые К тактов цикла второй блок элементов И закрыт (отсутствует сигнал на втором управляющем входе 15) и обратная связь кодера не работает. В этих К тактах осуществляется процесс загрузки и выгрузки регистров 1.1 - 1оК кодера о При этом регистры 1 о 1 - 1.К последовательно по

99976

течение последующих n-К тактов в схеме кодера выполняется вычисление контрольных символов кодового слова по поступающим в данном цикле на входы 13 информационным символам. При этом первые из них, п-2К тактов первый блок 4 элементов И открыт, а остальные К тактов закрыт.

0

5

0

5

0

5

0

5

В i-м (,n) такте работы кодера на выходы бтока 4 поступает очередной символ А С помощью первого - К-го преобразователей 3.1 - З.К кода, первого - К-го блоков 2„1 - 2.К cyN маторов по модулю два выполняете о1---- редной шаг деления на порождающий ь-v гочлен g(x), Преобразователи 3.1, 3„2,0.,,3.(К-1), кода символов реализуют процедуру умножения содержимого К-го регистра на постоянные множители соответственно g,,g7,..., g g . На информационных входах регистров 1.1-1.К формируется информация о следующем состоянии этих регистров, исходя из формулы (1). С помощь блоков 6о1 - 6.(К-1), 6ДК+1), 6. ( свертки по модулю два и соединителя на выходе первого сумматора 8 формируется сигнал четности следующего ее тояния содержимого регистров 1.1-1.К согласно правой части формулы (5)„ По окончании 1-го такта по тактовому сигналу, поступающему на тактовый вход 16, сигнал четности с выхода первого сумматора 8 запоминается в первом триггере 11, а информация с выходов блоков 2.1-2„К переписывается в регистры 1.1-1.К.

В следующем (1+1)-м такте с помощью блоков 6.1 - 6.К свертки по модулю два на выходе второго сумматора 9 формируется сигнал четности содержимого регистров 1.1 - 10К согласно левой части формулы (5)„ Сформированный с помощью этих блоков сигнал четности сравнивается путем суммирования по модулю два в третьем сумматоре 10 с ранее сформированным в i-м такте сигналом четности, хранящемся в

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

тактовым сигналам, поступающим на так- 50 пеРв°м триггере 11. Если данные два

тозый вход 16, заносятся первые К информационных символов, поступающие на информационные входы 13 в данном цикле, а на первые выходы 18 последовательно поступают К контрольных символов предыдущего кодового слова, полученных в предыдущем цикле работы кодера По окончании данных К тактов второй блок 5 элементов И замыкается. В

сигнала четности различны, то на выходе третьего сумматора 10 формируется сигнал сбоя, который по окончании (i+1)-ro такта по тактовому сигналу, поступающему на тактовый вход 16, запоминается во втором триггере 12. Одновременно в (i+O-м такте формируется с помощью блоков 6.1 - 6.(К-1), 6.(К+1), 6.(К+2) свертки по модулю

два, соединителя 7 и первого сумматора 8 сигнал четности следующего состояния регистров 1.1 - 1.К, который по тактовому сигналу, поступающему на тактовый вход 16, запоминается в первом триггере 11. На информационных входах регистров 1.1 - 1.К формируется информация о следующем состоянии этих регистров аналогично, как в i-м J такте, и т„д. Сигнал сбоя, если сбой имел место, с выхода второго триггера 12 передается на второй выход 19 кодера.

Рассмотрим пример для случая К 4 конечного поля Галуа GF(2 ), образованного неприводимым многочленом Х4+ L X + 1, и порождающего многочлена g(x) (x+c/)(x+o/1)(xV3)(xW) -г Л x2Wx W.

Приведем формулу (5) для этого слу2

(; i Al%ii R(;) j -i

+ : ).

Для этого примера преобразователи 3.1 - 304 кода символов (фиг. 2) выполнены на элементах ИСКЛЮЧАЮЩЕЕ ИЛИ 20. Указанное выполнение этих преоб- ра-ователей обеспечивает умножение входного кода символов на постоянные коэффициенты «/, о/3, , оС. Ъ в поле Галуа GF(24).

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

, поступающую в i-м такте на вход олока 7, которая является содержимым К-го регистра и может быть представлена в виде элемента конечного поля Галуа GF(24), следующим вектором

R

()

Выполняя умножение в конечном поле Галуа GF(2) вектора R ( к на постоянный коэффициент о/ , получим следующее выражение

(6)

Q

0

5

35

40

45

50

55

Определим свертку по модулю два выражения (6):

2(R(k с 1) (а3+аг+а1+а0)+(аг+а1+а0) + +(а,+ae)+(a3+a2+a1)al+a.

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

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

Устройство для кодирования циклических кодов, содержащее первый блок элементов И, информационные входы которого являются информационными входами устройства, первый - К-й буферные регистры (К - число контрольных символов в кодовом слове циклического кода), выходы К-го буферного регистра соединены с информационными входами второго блока элементов И и являются первыми выходами устройства, выходы второго блока элементов И подключены к входам первого - К-го преобразователей кода, выходы которых соединены с первыми входами одноименных блоков сумматоров по модулю два, выходы которых подключены к информационным входам одноименных буферных регистров, тактовые входы которых объединены и являются тактовым входом устройства, управляющие входы первого и второго блоков элементов И являются соответственно первым и вторым управляющими входами устройства, выходы первого блока элементов И и первого - (К-1)-го буферных регистров подключены к вто- I м входам соответственно первого - К-го блоков сумматоров по модулю два, отличающееся тем, что, с целью повышения достоверности в работе устройства за счет обеспечения аппаратного контроля правильности его функционирования, в устройство введены блоки свертки по модулю два, соединитель, первый - третий сумматоры по модулю два и первый и второй триггеры, установочные входы которых объединены и являются установочным входом устройства, тактовые входы триггеров объединены и подключены к тактовому входу устройства, входы первого - (К+1)-го блоков свертки по модулю два подключены к выходам соответственно первого - К-го буферных регистров и первого блока элементов И, входы и ВЫходы соединителя подключены соответственно к выходам второго блока элементов И и входам (К+2)-го блока свертки по модулю два, выходы первого - (К-1)- го блоков свертки по модулю два соедийены с соответствующими входами первого и второго сумматоров по модулю

«

J.

Фиг. 2

два, выходы которых подключены соответственно к информационному входу первого триггера и первому входу третьего сумматора по модулю два, выходы (К+1)-го и (К+2)-го блоков свертки по модулю два соединены с соответствующими входами первого сумматора по модулю два, выход К-го блока свертки по модулю два соединен с соответствующим входом второго сумматора по модулю два, выход первого триггера подключен к второму входу третьего сумматора п модулю два, выход которого соединен г. информационным входом второго тригге ра, выход которого является вторым входом устройства.

«з

S

§

I

J

фиг,. J

«м

V Ч)

«J

5