Устройство для кодирования циклических кодов

 

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

А1

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

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

РЕСПУБЛИН

„., Я0„„1569997 (1)5 Н 03 M 13/00 13/02

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

Н A ВТОРСНОМ,Ф СВИДЕТЕЛЬСТВУ

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

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

ПРИ CHHT СССР (21) 4477343/24-24 (22) 23.08.88 ,(46) 07.06.90. Бюл. №- 21 (71) Курский политехнический институт (72) В.В. Гвоздев, А.П. Типикин и С.И. Егоров (53) 681.326(088.8) (56) Питерсон У., Уэлдон Э. Коды, исправляющие ошйбки. — M.: Мир, 1976, с. 199 — 200, фиг. ?.6.

Патент США ¹ 4527269, кл. G 06 Р 11/12 1985. (54) УСТРОЙСТВО ДЛЯ КОДИРОВАНИЯ ЦИК ЛИЧЕСКИХ КОДОВ

2 (57) Изобретение относится к вычислительной технике. Его использование в системах хранения и обработки цифровой информации позволяет упростить устройство и повысить достоверность его работы за счет аппаратного контроля правильности его функционирования.

Устройство содержит буферные регистры

1, блоки 2 сумматоров по модулю два, преобразователи 3 кода и блоки 4,5 элементов И. Цель достигается благодаря введению блоков 6 свертки по модулю два, соединителя 7, сумматоров

8-10 по модулю два и .триггеров 11,12.

3 ил.

1569997

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

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

На фиг. 1 изображена функциональ1О

; ная схема устройства; на фиг. 2 и 3—, примеры выполнения соответственно преобразователей кода и соединителя, Устройство содержит буферные ре гистры 1 числом К (К вЂ” количество

,контрольных символов в кодовом слове

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

Принцип аппаратного контроля устройства для кодирования (кодера) ос.нован на методе предсказания следую щего состояния содержимого регистров

1.1 — 1.К по четности (по модулю два), зная алгебраические правила функционирования кодера. Кодер циклического кода (фиг. 1) построен по схеме деления на порождающий многочлен g(z), содержимое регистров 1.1, 1.2,..., 1.(К-1), 1.К в i-м такте обозначим

Определим содержимое регистров 1,1, 1.2,...,1.(К-1), 1.К в (i+1)-м такте, зная алгебраические правила функционирования кодера, как следующее." (1б1) (11 (i l

+ Rq g1

R! )= R(+ R( к И2 (1) (1+1) ((l (1)

К-2 к g к-1

R"" = R + R(! - g

К k1 К К» (iI 50 где А — символ на информационном входе 13 в i-м такте;

К » а »...»ак,»8 — кОэффициенты сооТветственно при о К 2 К-(,х, ° ° .,х

55 в порождающем многочлене к К-1 k-2

g(x)=х + g„x + g„,х +...+g2x+g, (1б1) (i) (i)

XR(= ф (А +К„g)

° ° ° (2) — P(R )+ R - ).

К к к

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

)=1 (3) К-1,» — обозначение суммирования по модулю два. где (1б1)

Подставляя в (3) вместо R их вы.) ражения из системы формул (2), раскрывая скобки и изменяя порядок суммирования в последнем члене, получим к ,7 3R> )ьА + ВК- +

Ж(К „ . g ). (4) к к

Поразрядную сумму,» я, можно

j>1 представить соответствующим элеменК том g =, g. конечного .поля Галуа р 3 (1

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

+,й (R„ . К,) ° (5) Блок 6. (К+1) свертки по модулю два (i) реализует Х А, блоки 6. 1-6.(К-1) реализуют соответственно gR — фК

1 К-1 в i-м такте, соединитель 7 и блок

6.(К+2) реализуют,®(R „ . gр), nep(ij циклического кода, которые являются элементами конечного поля Галуа

ce(g") .

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

5 15699 вый сумматор 8 реализует % A )+

К-f

+ Q К + )э(К „g,) . Блоки 6.1

ja)

6.К свертки по модулю два реализуют

5 ()б1) ),!б1) соответственно К, — фК „в (i+1)-м такте, второй сумматор 9 реализует (i+ t)

)а1 10

Приведем описание работы устройства для кодирования:,. циклических кодов на примере схемы кодера кодов Рида—

Соломона с порождающим многочленом

g(x)=(x+4 ) (xM )... (х+() (хМ ) г I+I где с(,Ы а("б"-, Ы "+" — элементы конечного поля Галуа GF(2 .) характеристики два (r e(0, 1, 2,..., 2 -2 )..

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

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

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

В последующих К тактах цикла первый блок 4 элементов И закрыт (отсут- 40 ствует сигнал на первом управляющем входе 14). Первые К тактов цикла второй блок элементов И закрыт (отсутствует сигнал на втором управляющем входе 15) и обратная связь кодера не 45 работает. В этих К тактах осуществляется процесс загрузки и выгрузки регистров 1.1 — 1.К кодера. При этом регистры 1.1 — 1.К последовательно по тактовым сигналам, поступающим на так- 50 тозый вход 16, заносятся первые К информационных символов, поступающие на информационные входы 13 в данном цикле, а на первые выходы 18 последоваTeJIsHo поступают К KQHTpoJIbHblx сииво 55 лов предыдущего кодового слова, полученных в предыдущем цикле работы кодера. По окончании данных К тактов второй блок 5 элементов И замыкается. В

97

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

4 элементов И открыт, а остальные К тактов закрыт.

В i-м (i=i,n) такте работы кодера на выходы блока 4 поступает очередной символ А . С помощью первого— ())

К-ro преобразователей 3. 1 — 3. К кода, первого — К-ro блоков 2.1 — 2.К .сумматоров по модулю два выполняется о;;редной шаг деления на порождающий мн.:гочлен g(x)„ Преобразователи 3.1, 3.2,..„ 3.(К-1), З.К кода символов реализуют процедуру умножения содержимого -ro регистра на постоянные множители соответственно g,,g

g . На информационных входах

К-Р K регистров 1.1-1.К формируется информация о следующем состоянии этих регистров, исходя из формулы (1). С помощью блоков 6.1 — 6.(К-1), 6.(К+1), 6.(К+=. свертки по модулю два и соединителя на выходе первого сумматора 8 формируется сигнал четности следующего сс . тояния содержимого регистров 1. 1-1.К согласно правой части формулы (5)..

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

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

1569997 два, соединителя 7 и первого сумматора 8 сигнал четности следующего состояния регистров 1.1 — 1.К, который

° ° ° о тактовому сигналу, поступающему на

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

2 передается на второй выход 19 ко ере.

Рассмотрим пример для случая К = 415 конечного поля Галуа GF (2 4), образованного неприводимым многочленом Х +

Ф

+ Х + 1, и порождающего многочлена (х) = (х+ Ы) (х+ ) (х+ ) (х+, 4) =х +, 1э х э+

+,! 6 х й+ Ы э х +,(10

Приведем формулу (5) для этого слу)as ! ;в R = А + g g R, +

3 J

+ X(R", d") °

Для этого примера преобразователи

3.1 — 3.4 кода символов (фиг, 2) выполнены на элементах ИСКЛЮЧАЮЩЕЕ ИЛИ ,20. Указанное выполнение этих преоб30 разователей обеспечивает умножение входного кода символов на постоянные коэффициенты о(", Ы, (, с(в поле

Галуа СР(2 ).

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

К-ro регистра и может быть представлена в виде элемента конечного поля

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

Выполняя умножение в конечном поле

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

55 а+а +а+а, til «a,+ а,+ а, R e а,+ а, аз+ a>+ а, (6) Определим свертку по модулю два выражения (6):

P(R „. g )=(а +а. +а,+а,)+(а +а,+а,)+

+(> +ао )+(аэ+а1+а1) а +аь

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

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

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

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

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

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

1569997

М

М ь

Д

Фиг. 3

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

Техред M.Äèäûê Корректор М. Максимищинец

Редактор Н. Яцола

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

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

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

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