Устройство кодирования блоков информации

 

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

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

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

РЕСПУБЛИК (51) 4 Н 03 M 13/02

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

И А ВТ0РСНОМУ СВИДЕТЕЛЬСТВУ юг, 1

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3690614/24-09 (22) 12.01.84 (46) 07. 04.87. Бюл. У 13 (72) Л.М.Боголюбова, В.И.Рутковский и Г.А.Кабатянский (53) 621. 394. 14 (088. 8) (56) Патент США И- 3745528, кл. С 06 Р 11/12, 1971.

Блох Э.Л., Зяблов В.В. Обобщенные каскадные коды. — M. Связь, 1976, с. 108, рис. 3.40. (54) УСТРОЙСТВО КОДИРОВАНИЯ БЛОКОВ ИНФОРМАЦИИ

„„SU„„ l 302439 А1 (57) Изобретение относится к вычислительной технике. Цель изобретения— увеличение объема зашищаемой от ошибок информации. Устр-во содержит три вычислителя 1,2 и 5, коммутатор 3 и блок

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

2 и 5. 1 з.п. ф-лы, 4 ил.

C t) (1-1)

9 (5) (6) 1 13024

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

Цель изобретения является увеличе- 10 ние объема защищаемой от ошибок информации.

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

Устройство кодирования блоков ин" 20 формации содержит первый и второй вычислители 1 и 2, коммутатор 3, блок

4 управления, третий вычислитель 5, причем блок 4 управления содержит счетчик 6, первый элемент И-НЕ ?, пер-25 вый, второй и третий элементы И 8, 9 и 10 элемент 11 задержки, первый триггер 12, второй элемент И-НЕ 13, второй триггер 14, четвертый элемент

И 15, а первый. вычислитель содержит 30 риггеры 16 16в

Второй и третий вычислители 2 и 5 выполнены идентично и содержат первый блох 1? сумматоров по модулю 2, второй блок l8 сумматоров по модулю два и регистр 19.

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

В процессе кодирования устройство осуществляет формирование вектора, 40 (х ° ° °,х е, y,,y,,у. ), где х информационные элементы, а у; " проверочные элементы, в соответствии с проверочной матрицей 1...1...1 1 1 00

Н = ее.. ° .с ... е . -< 0 0 1 0

Ы . " ... " ) j 0 0 1, (1) где,а — примитивный элемент поля ГаGF (2Р)

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

2 и третьего 5 вычислителей разряд39 2 ность символов 1 = 8. Во втором 2 и третьем 5 вычислителях в качестве примитивного многочлена определяюще г 8 го поле Галуа GF,2 ), выбирают многочлен р(х) = 1 + х + ха+ х4+ хз.

Вклечение второго блока сумматоров

18 по модулю 2 между 1-4-ми разрядами регистра 19 и цепью его обратной связи призведено в соответствии со значениями коэффициентов этого многочлена.

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

Вычисление .проверочных, символов у, у. из информационных символов

Э уй х, х,„, ..., х в осуществляется в

2— - 1 предлагаемом устройстве в соответствии со следующими выражениями:

2 1 е у = Эх, (2);

i--0

2-1 е

У =) ex;cl (3);

1=1

2.-1

i=O

Первый проверочный символ у пред<1 ставляет собой обычную контрольную сумму,по модулю два всех символов блока йнформацИИ.

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

При описании работы устройства пре дусматривается, чуо все операции вычисления проверочных символов осуществляются в поле GF (2 ), определяемом многочленом F (х) степени 1 с коэффициентами из поля GF (2 ) °

t!

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

3 на выходы устройства.

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

4 управления, поступает на выход второго элемента И-НЕ 13 и устанавливает в нулевое состояние триггеры 16—

16 первого вычислителя 1, регистры

19 второго и третьего вычислителей

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

Далее в устройстве осуществляется формирование проверочных символов 25 у, у и у из поступающих информа-.

2 з

ЦИОННЫХ СИМВОЛОВ Х 1 Х ° Р Х о согласно соотношениям (2), (3) и (4) .

Период кодирования каждого символа х . составляет четыре тактовых 30

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

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

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

Первый сигнал синхронизации формируется на выходе второго элемента И

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

7, входы которого соединены с прямым

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

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

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

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

Синхронизация работы триггеров 16—

16 осуществляется по переднему фронту первого сигнала управления.

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

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

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

t о о о означает: у = х, у.= О, у х .. Условие у = 0 обеспечивается во втором

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

2. По заднему фронту этого сигнала управления второй триггер 14 устанав" ливается в единичное состояние и открывает четвертый элемент И 15 для прохождения последующих вторых сигналов управления.

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

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

По окончании периода кодирования последнего информационного символа в первом, втором, третьем вычислителях

1,2 и 5 содержатся соответственно проверочные символы этого блока у

1 у, у, которые поочередно передайтся через коммутатор 3 на выход устройства при поступлении на адресный вход устройства соответствующих кодов адреса. I. Устройство кодирования блоков информации, содержащее первый и второй вычислители, информационные входы которых объединены с первым информационным входом коммутатора, второй и третий информационные входы которого соединены соответственно с информационными выходами первого и второго вычислителей, а также блок управления, тактовый выход которого соединен с входом синхронизации первого вычислителя, а адресный вход устройства подключен к адресному входу коммутатора, о т л и ч а ю щ е е с я тем, что, с целью увеличения объема защищаемой от ошибок информации, в него введен третий вычислитель, а блок управления выполнен в виде счетчика, первый вход которого соединен с первым входом первого элемента И-НЕ, второй вход которого объединен с первым входом первого элемента И и подключен к второму выходу счетчика, третий выход которого соединен с вторым входом первого эЛемента И и первым входом второго элемента И, первый вход третьего элемента И соединен с выходом первого элемента И-НЕ, второй вход объединен с вторым входом второго элемента И и подключен к выходу эле— мента задержки, выход первого триггера соединен с первым входом второго элемента И-НЕ, выход второго триггера

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

18 сумматоров представляет собой результат сложения по модулю для значений сигнала в цепи обратной связи, поступающего на первые входы второго блока 18 сумматоров, и значений сиг — !5 налов с выходов первого, второго и третьего (j + 1)-х разрядов регистра

19, соответственно поступающих на вторые входы второго блока 18 сумматоров. Тем самым за один такт сдвига в 2() регистре 19 осуществляется умножение

его содержимого на примитивный элемент поля GF (2 ) и вычисление первоР (i- s ) го слагаемого у из выражения (5).

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

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

1 регистра 19.

Формирование проверочного символа у осуществляется в третьем вычислиз теле 5, синхронизация работы которого осуществляется по заднему фронту импульсов, поступающих на вход синхронизации регистра 19 с выхода третьего 40 элемента И 10. Первые сигналы управления поступают на вход управления регистра 19 с выхода первого элемента

И 8 блока 4 управления.

В течение каждого периода кодиро- 45 . вания символа х при поступлении первых двух импульсов второго сигнала синхронизации и при низком уровне сигнала управления происходит циклический сдвиг содержимого регистра 5О

19 на два разряда вправо, что обеспечивает умножение его содержимого на элемент <с в поле GF (? ) и вычисле° 8 ние слагаемого у . Затем при (i -1) з поступлении третьего импульса второго 55 сигнала синхронизации и при высоком уровне первого сигнала управления происходит занесение в регистр 19 результата поразрядного сложения по

1302439

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

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

2. Устройство по.п.1, о т л и ч аю щ е е с я тем, что второй и третий вычислители выполнены одинаково и содержат первый и второй блоки сумматоров по модулю два и регистр, причем первые входы первого блока сумматоров по модулю два соединены с соответствующими выходами регистра, а выходы — с первыми входами соответствующих разрядов регистра, первые входы второго блока сумматоров по модулю два и второй вход первого разряда регистра соединены с выходом ?-ro разряда регистра, а вторые входы. второго блока сумматоров по модулю два соединены соответственно с выходами j-x разрядов регистра, где ? j а(? — 1) и принимает значения степеней х примитивного многочлена, определяющего поле Галуа GF (2 ), выходы второго блока сумматоров по модулю два соединены соответственно с вторыми входами () + 1)-х разрядов регистра, вторые входы S-x разрядов регистра, где S принимает значения два ...,1 sa исключением значений j соединены с выходами ($ — 1)-х разрядов регистра, входы управления, синхронизации и установки нуля регистра являются соответствующими входами вычислителя, вторые входы первого блока сумматоров по модулю два являются инфермационными входами вычислителя, а .выход регистра — выходом вычислителя.

1302439

Иир. lюУ

Фар. Ю ui 0 (мУ) Фаа Ю

Составитель А.Андрианов:-,е

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

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открьгтий

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

Заказ 1225/56

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