Устройство кодирования блоков информации Советский патент 1987 года по МПК H03M13/51 

ность символов- f 8. Во втором 2 и третьем 5 вычислителях в качестве примитивного многочлена, определяЮщел

ГО поле Галуа GF 42 ), выбирают мно- 5 гочлен F(x) 1 + х + х. Bклк чeниe второго блока сумматоров 18 по модулю 2 между 1-4-ми разрядами регистра 19 и цепью его обратной связи призведено в соответствии со зна-

Изобретение относится к вычисли тельной технике и передачи данных и может быть использовано для помехоустойчивого кодирования цифровой информации, представленной в виде блоков из 2 1-разр ядных двоичных элементов (J - натуральное число), например, при защите от ошибок устройств со страничной организацией данных.

Цель изобретения является увеличе- JO чениями коэффициентов этого много- ние объема защищаемой от ошибок инфор- члена, мации.Коммутатор 3 предназначен для переНа фиг.1 представлена схема устрой- дачи на выходы устройства информации ства кодирования блоков информации; с информационного входа устройства на фиг.2 - вариант выполнения первого 15 или с выходов одного из трех вычисли- вычислителя; на фиг.З - то же, второ- телей, в зависимости от кода адреса, го (третьего) вычислителя; на фиг.4 - прступающего на адресный вход устрой- времённая диаграмма работы устрой- ства. ства.Вычисление прове рочных, символов

Устройство кодирования блоков ин- 20 у, , у , у из информационных символов формации содержит первый и второй х, х/, ..., х е ., осуществляется в вьгчислители 1 и 2, коммутатор 3, блок предлагаемом устройстве в соответ- 4 управления, третий вычислитель 5, ствии со следуннцими выражениями: причем блок 4 управления содержит

П®х,

(2)J

30

)©Xjd t

г -,

(3);

У. Гех,. -

i O

(4)

счетчик 6, первый элемент И-НЕ 7, пер- вый, второй и- третий элементы И 8, 9 и 10, элемент 11 задержки, первый триггер 12, второй элемент И-НЕ 13, второй триггер 14, четвертый элемент И 15, а первый. вьrчиcлитeJIь содержит триггеры 16 - 16g.

Второй и третий вычислители 2 и 5 выполнены идентично и содержат п ервый Первый проверочньй символ у пред- блок 17 сумматоров по модулю 2, второй ставляет собой обычную контрольную блок 18 сумматоров по модулю два и 35 сумму |ПО модулю два всех символов регистр 19.блока йнформащй.

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

В процессе кодирования устгройство осуществляет формированиё BekTopa . (Хо,...,, , у ,у, ,у.,),- где X. - информационные элементы, а у проверочные элементы, в соответствии с проверочной матрицей

Вычисления у и ; осуществляются с использованием следующей схемы вычисления:

40

U) „(i-i;

У,

У У г

сс©х. ;

(i-) .2,

ril@Xj

(5) (6)

1

1

1

.2Г

dU« сА. dL js .2; .«(a-i) -d

1100 0010

i о о 1

(1)

где - примитивный элемент поля Га- многочленом F (х) степени 1 с коэффи- луа GF (2).50 циентами из поля GF (2 ).

Первый, второй и третий вычислитегг При этой от источника информации на ли 1, 2 и 5 осуществляют формирование входы первого, второго и третьего вы- соответственно первого, второго и числителей 1,2 и 5 и коммутатора 3 пос- третьего проверочных символов для каж- тупают параллельно поразрядно симво- дого блока информации, поступающего 55 блока информации (фиг.4е), на вход на информационный вход устройства. В синхронизахщи счетчика 6 подаются приведенных примерах (фиг,2 и 3) кон- тактовые импульсы (фиг.4а), на вход кретной реализации первого 1, второго установки нуля счетчика 6 - сигнал 2 и третьего 5 вычислителей разряд- посыпки (фиг.4б), сопровождающий посность символов- f 8. Во втором 2 и третьем 5 вычислителях в качестве примитивного многочлена, определяЮщел

ГО поле Галуа GF 42 ), выбирают мно- гочлен F(x) 1 + х + х. Bклк чeниe второго блока сумматоров 18 по модулю 2 между 1-4-ми разрядами регистра 19 и цепью его обратной связи призведено в соответствии со зна-

20 у, , у , у из информационных симв х, х/, ..., х е ., осуществляется предлагаемом устройстве в соответ ствии со следуннцими выражениями:

П®х,

(2)J

30

)©Xjd t

г -,

(3);

У. Гех,. -

i O

(4)

Первый проверочньй символ у п ставляет собой обычную контрольну 35 сумму |ПО модулю два всех символов блока йнформащй.

Вычисления у и ; осуществляются с использованием следующей схемы вычисления:

0

U) „(i-i;

У,

У У г

сс©х. ;

(i-) .2,

ril@Xj

(5) (6)

45 При описании работы устройства пре дусматривается, чуо все операции вычисления проверочных символов осущес- твляются в поле GF (2 ), определяемом

многочленом F (х) степени 1 с коэффи- 50 циентами из поля GF (2 ).

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

Кодирование каждого блока информации начинается с установки устройства в. исходное состояние. Первый

тактовый импульс, который совпадает cfg единичном второго триггера 14.

сигналом посылки и сигналом с нулевого выхода первого триггера 12 блока 4 управления, поступает на выход второго элемента И-НЕ 13 и устанавливает в нулевое состояние триггеры 16 - 16 первого вычислителя 1, регистры 19 второго и третьего вычислителей 2 и 5 и второй триггер 14 блока 4 управления. После этого по заднему фронту этого же тактового импульса первый триггер 12 блока 4 управления устанавливается в единичное состояние и закрывает второй элемент И-НЕ 13.

Далее в устройстве осуществляется формирование проверочных символов

У.

из поступающих информа-.

Формирование проверочного символа у осуществляется во втором вычислителе 2. Символы кодируемой информации поступают на первые входы первого блока. 17 сумматоров. Первый сигнал синхронизации поступает с выхода второго элемента И 9 на вход- синхронизации регистра 19 второго вычислителя 2 на вход управления которого поступает второй сигнал управления с выхода четвертого элемента И 15, и определяют режим его работы. При этом низкий уровень сигнала управления задает режим циклического сдвига, а высокий уровень - режим занесения через соот19.

Кодирование символа х производится с учетом наличия

матрице Н (1) вектора столбца

в проверочной II , что

означает: ловие у вычислителе

о

V

X

о

0. У

X,

Усционных символов X , X ,...,x,j

согласно соотношениям (2), (3) и (4). Период кодирования каждого символа X . составляет четыре тактовых ЗО импульса. В блоке 4 управления в течение этого периода вырабатывается на выходе первого элемента И 8 один сигнал управления (фиг.4д), на выходе

второго элемента И 9 два сигнала син-. ветствующие входы регистра хронизации для второго вычислителя 2 (фиг.4в) и на выходе третьего элемента И 10 три сигнала синхронизации для третьего вычислителя 5 (фиг.4г). Тактовые импульсы в блоке 4 управления 40 поступают на счетный вход счетчика 6 и через элемент задержки 11, время задержки которого определяется временем переходных процессов в счетчике

6и задержкой первого элемента И-НЕ

7- на входы второго и третьего элементов И 9 и 10.

Первый сигнал синхронизации формируется на выходе второго элемента И 9 при совпадении на его входах сигна- Q 2. По заднему фронту этого сигнала ла с выхода элемента 11 задержки,сиг- управления второй триггер 14 устанав- нала посьшки и сигнала нулевого состояния счетчика 6. Второй сигнал синхронизации формируется на выходе третьего элемента И 10 при совпадении сигнала с выхода элемента 11 задержки, сигнала посьшки и единичного сигнала с выхода первого элемента И-НЕ 7, входы которого соединены с прямым

° О обеспечивается во втором 2 запретом занесения символа Xjj в регистр 19. Для этого низ- 45 кий уровень сигнала с единичного выхода второго триггера 14 запрещает прохождение первого сигнала управления через четвертый элемент И 15 на вход управления второго вычислителя

ливается в единичное состояние и открывает четвертый элемент И 13 для прохождения последующих вторых сигналов управления.

В течение каждого периода кодирования последующих символов х - в регистре 19 по заднему фронту первого

24394

выходом первого разряда и с инверсным выходом второго разряда счетчика 6,

Первый сигнал управления формируется на выходе первого элемента И 8 при нулевом состоянии счетчика 6, а второй сигнал управления формируется на выходе четвертого элемента И 15 при нулевом состоянии счетчика 6 и

У,

Формирование проверочного символа осуществляется накапливанием в

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

Формирование проверочного символа у осуществляется во втором вычислителе 2. Символы кодируемой информации поступают на первые входы первого блока. 17 сумматоров. Первый сигнал синхронизации поступает с выхода второго элемента И 9 на вход- синхронизации регистра 19 второго вычислителя 2, на вход управления которого поступает второй сигнал управления с выхода четвертого элемента И 15, и определяют режим его работы. При этом низкий уровень сигнала управления задает режим циклического сдвига, а высокий уровень - режим занесения через соот19.

ветствующие входы регистра

Кодирование символа х производится с учетом наличия

матрице Н (1) вектора столбца

в проверочной II , что

ветствующие входы регистра

X

о

0. У

X,

Усвходы регистра

обеспечивается во втором 2 запретом занесения симветствующие входы регистра

2. По заднему фронту этого сигнала управления второй триггер 14 устанав-

вола Xjj в регистр 19. Для этого низ- кий уровень сигнала с единичного выхода второго триггера 14 запрещает прохождение первого сигнала управления через четвертый элемент И 15 на вход управления второго вычислителя

2. По заднему фронту этого сигнала управления второй триггер 14 устанав-

ливается в единичное состояние и открывает четвертый элемент И 13 для прохождения последующих вторых сигналов управления.

В течение каждого периода кодирования последующих символов х - в регистре 19 по заднему фронту первого

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

блока 18 сумматоров, и значений сиг- 15 последнего информационного символа в налов с выходов первого, второго и первом, втором, третьем вычислителях третьего (j + 1)-х разрядов регистра 1,2 и 5 содержатся соответственно 19, соответственно поступающих на проверочные символы этого блока у, вторые входы второго блока 18 суммато- У,.,, ров. Тем самым за один такт сдвига в регистре 19 осуществляется умножение его содержимого на примитивный элемент поля GF (2 ) и вычисление первого слагаемого у, из вьфажения (5) . 25 Ф о р м-у л а

Затем по заднему фронту второго импульса первого сигнала синхронизации 1. Устройство кодирования блоков

при высоком уровне второго сигналаинформации, содержащее первый и втоуправления происходит занесение врой вычислители, информационные вхорегистр 19 с выходов первого блока 17 30ды которых обт единены с первым инфорсумматоров результатов поразрядногомационным входом коммутатора, второй сложения по модулю два значения симу , которые поочередно передается 20 через коммутатор 3 на выход устройства при поступлении на адресный вход устройства соответствующих кодов адреса.

изобретения

и третий информационные входы которого соединены соответственно с информационными выходами первого и второго

вола X с содержимым всех разрядов

и третий информационные входы которого соединены соответственно с информационными выходами первого и второго

регистра 19.

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

низации регистра 19 с выхода третьего 40 отличающееся тем, что, с

элемента И 10. Первые сигналы управления поступают на вход управления регистра 19 с выхода первого элемента И 8 блока 4 управления.

В т.ечение каждого периода кодиро- 45 вход которого соединен с первым вхования символа х при поступлении первых двух импульсов второго сигнала синхронизации и при низком уровне сигнала управления происходит циклический сдвиг содержимого регистра 19 на два разряда вправо, что обеспечивает умножение его содержимого на элемент ы в поле GF (2) и вычисле -) . 2

ДОМ первого элемента И-НЕ, второй вход которого объединен с первым входом первого элемента И и подключен к второму выходу счетчика, третий вы- 50 ход которого соединен с вторым входом первого элемента И и первым входом второго элемента И, первый вход третьего элемента И соединен с выходом

ние слагаемого Затем при первого элемента И-НЕ, второй вход поступлении третьего импульса второго 55 объединен с вторым входом второго сигнала Синхронизации и при высоком элемента И и подключен к выходу эле- уровне первого сигнала управления . мента задержки, выход первого тригге- происходит занесение в регистр 19 ре- ра соединен с первым входом второго зультата поразрядного сложения по элемента И-НЕ, выход второго триггера

модулю два символов х. с содержимым регистра 19.

Кодирование блока информации заканчивается тем, что в блоке 4 управления

по заднему фронту сигнала посыпки устанавливается в нулевое состояние первый триггер 12, сигнал с выхода которого подготавливает прохождение первого тактового импульса через второй элемент И-НЕ 13 для установки исходного состояния устройства перед началом кодирования следующего блока информации.

По окончании периода кодирования

последнего информационного символа в первом, втором, третьем вычислителях 1,2 и 5 содержатся соответственно проверочные символы этого блока у, У,.,, Ф о р м-у л а

у , которые поочередно передается через коммутатор 3 на выход устройства при поступлении на адресный вход устройства соответствующих кодов адреса.

изобретения

мационным входом коммутатора, второй

и третий информационные входы которого соединены соответственно с информационными выходами первого и второго

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

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

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

ДОМ первого элемента И-НЕ, второй вход которого объединен с первым входом первого элемента И и подключен к второму выходу счетчика, третий вы- 50 ход которого соединен с вторым входом первого элемента И и первым входом второго элемента И, первый вход третьего элемента И соединен с выходом

7I

соединен с первым входом четвертого элемента И, вход установки нуля счетчика соединен с входом установки нуля пе рвого триггера, информационным входом первого триггера, .вторым вхо- дом второго элемента И-НЕ и третьими входами второго и третьего элементов И, входы синхронизации счетчика и первого триггера соединены с третьим входом второго элемента И-НЕ и входо элемента задержки, выход второго элемента И-НЕ соединен с входом установки нуля второго триггера, выход первого элемента И соединен с вторым вхдом четвертого элемента И и входом синхронизации второго триггера, при этом выход второго элемента И-НЕ соединен с входами установки нуля первого, второго и третьего вычислителей, выход первого элемента И соединен с входом синхронизации первого вычислителя и с входом управления третьего вычислителя, выход четвертого элемента И соединен с входом,управления втрого вычислителя, выход второго эле- мента И соединен с входом - синхрониэа ции второго вьгаислителя, выход третьего элемента И соединен с входом синхронизации третьего вычислителя,.

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

2. Устройство no.n.l, отлич ющееся тем, что второй и тр вычислители вьшолнены одинаково и держат первый и второй блоки сумм ров по модулю два и регистр, прич первые входы первого блока суммат ров по модулю два., соединены с соо ствующими выходами регистра, а вых ды - с первыми входами соответству щих разрядов регистра, первые вход второго блока сумматоров по модулю два и второй вход первого разряда гистра соединены с выходом 1-го р ряда регистра, а вторые входы вто блока сумматоров по модулю два со нены соответственно с выходами jразрядов регистра, где f j (I - и принимает значения степеней х п митивного многочлена, определяюще поле Галуа GF (2 ), выходы второг блока сумматоров по модулю два со нены соответственно с вторыми вхо (J + 1)-х разрядов регистра, втор входы S-X разрядов регистра, где принимает значения два ...,1 за лючением значений j, соединены с дами (S - 1)-х разрядов регистра, входы управления, синхронизации и тановки нуля регистра являются со

рые входы первого блока сумматоро по модулю два являются инф«рм4цио ми входами вычислителя, а выход р чра - выходом вычислителя.

Г

ветствующими входами вычислителя.

8

2. Устройство no.n.l, отличающееся тем, что второй и третий вычислители вьшолнены одинаково и содержат первый и второй блоки сумматоров по модулю два и регистр, причем первые входы первого блока сумматоров по модулю два., соединены с соответствующими выходами регистра, а выходы - с первыми входами соответствующих разрядов регистра, первые входы второго блока сумматоров по модулю два и второй вход первого разряда регистра соединены с выходом 1-го разряда регистра, а вторые входы второго блока сумматоров по модулю два соединены соответственно с выходами jx разрядов регистра, где f j (I - 1) и принимает значения степеней х примитивного многочлена, определяющег о поле Галуа GF (2 ), выходы второго блока сумматоров по модулю два соединены соответственно с вторыми входами (J + 1)-х разрядов регистра, вторые входы S-X разрядов регистра, где S принимает значения два ...,1 за исключением значений j, соединены с выходами (S - 1)-х разрядов регистра, входы управления, синхронизации и установки нуля регистра являются соотвторые входы первого блока сумматоров по модулю два являются инф«рм4ционны- ми входами вычислителя, а выход регис- чра - выходом вычислителя.

п

Фиг. 4

Составитель А.Андрианов Редактор Н.Гунько Техред Л.Слейник Корректор Н.Король

Заказ 1225/56

Тираж 902.Подписное

ВНИШШ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

Изобретение относится к вычислительной технике. Цель изобретения - увеличение объема защищаемой от ошибок информации. Устр-во содержит три вычислителя 1,2 и 5, коммутатор 3 и блок 4 управления, состоящий из счетчика 6, двух эл-тов И-НЕ 7 и 13, четырех эл- тов И 8,9,10 и 15, эл-та 11 задержки и двух триггеров 12 и 14. Цель достигается введением вычислителя 5, формирующего дополнительный проверочный символ в процессе кодирования информационного символа. Устр-во по п.2 ф-лы отличается выполнением вычислителей 2 и 5. 1 з.п. ф-лы, 4 ил. . (Л Фиг. Мфес