Устройство для кодирования

 

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

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

И

PECflVSËÈК (51)4 Н 03 M 13 02

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

ПО ДЕЛАМ И306РЕТЕНИЙ И OTHPblTPM

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

К АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ (54) УСТРОЙСТВО ДЛЯ КОДИРОВАНИЯ (57) Изобретение относится K вычислительной технике. Его использование в системах передачи цифровой информации с обнаружением и исправлением групповых ошибок позволяет повысить (21) 3935479/24-24 (22) 3 1.05.85 (46) 07.12.86. Бюп. В 45 (72) А.И.Карпухин и В.С.Ракошнц (53) 681.325(088.8) (56) Патент США В 3781795, кл. G 06 F 11/08, опублик. 25.12.73.

Авторское свидетельство СССР

У 610312, кл. С 06 Р 5/02,20.10.75.

„„SU,„, 1275782 A 1 быстродействие и надежность функционирования. Устройство для кодирования содержит сдвиговый регистр, основной элемент И и блок управления.

Введение формирователя первого проверочного символа, 2t-1 формирователей последующего проверочного символа, 2е дополнительных элементов И н элемента ИЛИ; где t — - число ошибок, исправляемых выходным кодом устройства над полем СР(2 ), обеспечивает формирование требуемых проверочных символов с помощью операций сложения и вычитания, благодаря чему повьппаются надежность и быстродействие. 3 з.п.ф-лы, 5 ил.

1275782

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

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

На фиг. 1 изображена блок-схема устройства для кодирования; на фиг ° 2 — 4 — функциональные схемы соответственно формирователя первого проверочного символа, формирователя последующего проверочного символа и блока управления, на фиг. 5 — временные,диаграммы сигналов. устройство для кодирования содержит сдвиговый регистр 1, основной элемент И 2, блок 3 управления, формирователь 4 первого проверочного символа, 2t — 1 формирователей 5 последующего проверочного символа, 2t дополнительных элементов И 6, элемент ИЛИ 7, информационный и тактовый входы 8 и 9 и выход 10. Здесь

t — - число ошибок, исправляемых выход3т ным кодом устройства над полем СР(2 ).

Регистр 1 содержит 2ш разрядов, выходы ш первых его разрядов подключены к информационным входам блокЫ 3 управления и формирователя 4.

Формирователь 4 первого проверочного символа содержит (фиг. 2) первый второй и третий буферные регистры

11-8, вычитатель 14, преобразователь 15 кода, сумматор 16 и регистр

17 сдвига.

Формирователь 5 последующего проверочного символа содержит (фиг. 3) вычитатель 18, преобразователь 19 кода, первый и второй буферные регистры 20 и 21, сумматор 22 и регистр

23 сдвига.

Блок 3 управления содержит (фиг.4) счетчик 24, дешифратор 25, три элемента ЗАПРЕТ 26, первый элемент И 27 и 2t+1 вторых элементов И 28, информационные входы 29, выходы 30-40 с первого по (2t+9)-й.

Буферные регистры 11 — 13 формирователя 4 и буферные регистры 20 и

21 формирователя 5, а также регистры 17 и 23 сдвига формирователей 4 и 5 имеют по ш разрядов. Преобразо- $5 ватели 15 и 19 кода формирователей

4 и 5 осуществляют над входной велиЧ (2)

2 чиной Е преобразование d. = 1Оо где d.е СР(2 ") — примитивный элемент поля СР(2 ), Q+ — сложение по модулю два. Вычитатели 14 и 18 и сумматоры 16 и 22 формирователей 4 и 5 осуществляют соответствующие операции по модулю 2 -1. Первые входы вычитателя 18 каждого g --ro формирователя

5, где g g (1, 2t-1), являются инфор" мационными входами формирователя 5 вторые входы вычитателя 18 при этом соединены с шинами источников логических уровней в соответствии с двоичным кодов номера данного формирователя 5.

На фиг ° 5 показаны следующие сигналы: а — тактовые импульсы на тактовом входе 9, также на первом выходе 30 блока 3, б — к †. сигналы на выходах 31-39 соответственно с второго по девятый блока 3, л и м— сигналы на выходах (2С-1)-ro u (2t)-ro элементов И 28 блока 3, т.е. на (2t+7)-м и (2t+8)-м выходах этого блока 3, н — сигнал на (2t+9)-м выходе 40 блока 3 управления.

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

Информация, подлежащая кодировайию, разбивается на блоки по 2 -1

m-разрядных символов в каждом, являющихся показателями степени примитивного элементаЫЕСР(2 ) — корня

ln непроводимого многочлена степени ш.

Обозначим информационные символы К ъ

i=0,...,2 — 2, проверочные символы

К, j = 2 -1,...,2 + 2(t-1), где t— число исправляемых кодом ошибок.

Тогда первый проверочный символ получается из соотношения hl

К 2-2 о

К m с< =ф ck =cL ® P ® (+ Д "--> (1)

i --0 где (+) и @ — суммирование в поле

СР(2" ).

Введем функцию q (К) такую, что с(1 Q+aL Тогда с + 1. о((1 О+

®с 1 ) = 1 (Ко К 1 = i ° алее (1 ® к (а +к ) ч

О+< = + " d- 2, ив общем случае:

К; K.

< (+)о = Ф +Ч(о; 1 К 11 или, переходя к показателям степеней: а,. = К,+Ау(а. — К,).

12757S2

Обозначим Ъ; а., — К., тогда а,.

=К;+ (b) и а;,- К,. + 1(Ь ), 5 откуда Ъ, К. — К,.+ (Ъ. ) . .(2) Уравнение (2) является итерационной формулой для получения первого проверочноГо символа. 1О

Начальные условия: Ь K,- К .

Вычисление по формулам (2) и.(3). т.е ° операции сложения и вычитание осуществляют по модулю 2 -1. При этом

hl нужно иметь в виду, что К.=. 2 — 1 1S

1 it) не определено в кольце по модулю 2 -1

Поэтому

fall Рп (2 -1)+а = 2 " 1, где а „; любой элемент кольца. При 20

<2- 1 Т) этом Ы = 0 и К = 2 — 1 изымаются из суммы (1). Для учета этой ситуа«ции в устройство введен элемент И 27 .фиг. 4), выдающий запрет на выдачу управляющих сигналов с блока 3 уп- 25 равления.

Остальные f --e проверочные символы получают из соотношения:

2.-2

2 + 1 (— К. + 1 i

d = 0 oL

i--О

35 где «1 = 1,...,2t-1.

Аналогично формуле (2) получим:

На вход 9 устройства поступают блоки информации по 60 разрядов в сопровождении тактовых импульсов (фиг. 5), затем 56 тактов следует пауза для заполнения ее проверочными символами. Первые 4 такта следует О-й цикл, в течение которого заполняются первые 4 разряда сдвигового регистра 1, содержащего в рассматриваемом примере восемь разрядов. Затем следует

1-й цикл (5,6,7,8 такты), где по сигналу с второго выхода 31 блока 3 (фиг. 56) производится запись на регистр 11 первого символа информации и затем по сигналу с выхода 32 бло-. ка 3 (фиг. 56) — его перепись с ре:гистра 11 на регистр 12.

В следующем, втором цикле (9, 10, 11, 12 такты), производится вычитание из содержимого (К,) регистра 12 записанного в регистре 11 второго (К ) информационного символа на вычитателе .14, сложение полученного результата с нулем регистра 13 на сумматоре 16 и запись результата на регистр 17 по сигналу с выхода 33 блока 3 (фиг. 5 z). Одновременно по сигналу с выхода 35 блока 3 (фиг.5 e) результат вычитания с вычитателя 14 через вторые выходы формирователя

4 первого проверочного символа поступает на информационные входы формирователей 5 последующего проверочного символа, в которых на вычитателях 18 производится вычитание номера 1 формирователя 5 и запись полученной разности на регистр 20. и

Ь. К ° + (11) К I1i+ч(Ь. ) 40

- к. -ч- к.+ч(ь. ) (5)

1-1

\ i-1

Начальные условия: Ъ К -К вЂ” Ч (6) l о 1

Окончательный результат по форму- 45 лам (1) и (4) получается на 2 -м такте (i = 2 "-1). В- этом такте форму. лы (2) и (5) примут вид.

Ъ", =К „+ 1 (Ь ) (2 ) 50

- 2 2™-2 и ь - = к,„+ (2 -2)+ч(ь ) (5 )

2 -2 2 -2

Устройство для кодирования рабо- 55 тает следующим образом. (На фиг. 5 представлена временная диаграмма ра боты устройства при m=4 и t = 7).

По сигналу с выхода 32 блока 3. производится перепись на регистр 12 второго (К„) информационного символа, а по сигналу с выхода 34 блока

3 (фиг. 5д) — передача содержимого регистра 17 с преобразованием его в преобразователе 15 кода в регистр

13. Одновременно по сигналу с выхода 37 блока 3 (фиг. 5 y) производится сложение на сумматоре 22 содержимого регистра 20 с нулем регистра 21 и запись результата на регистр 23.

Третий цикл аналогичен второму за исключением того, что при сложении на сумматорах 16 и. 22 оба операнда в общем случае отличны от нуля, и по сигналу с выхода 36 блока

3 (фиг.5ж) осуществляется передача содержимого регистра 23 с преоб1275782

S разованием в преобразователе 19 кода в регистр 21.

Циклы с 4-го по 15-й аналогичны . третьему. При этом в 15-м цикле после передачи содержимого регистра 11 на регистр 12 регистр 11 обнуляется.

Далее, в 16-м цикле по сигналу с выхода 33 блока 3 на вычитателе 14 из содержимого регистра 12 вычитается нуль регистра 11 (формула 2 ) и ре- 1п эультат (содержимое регистра 12) йа сумматоре 16 складывается с содержимым регистра 13. Результат сложения, являющийся первым проверочным символом, записывается на регистр 17. Одновременно с вычитателя 14 информация поступает на вычитатель 18 где производится вычигп n тание величины - l(2 -2)=(-(2 -2)) ) = так как -(2 -2) =(2 -1)-(2 -2) =1 .

По сигналу с выхода 35 блока 3 результат вычитания записывается на регистр 20. Одновременно, по сигна" лу с выхода 36 блока 3 производится перепись содержимого регистра 23 (от предыдущего цикла) на регистр

21 с преобразованием в преобразователе 19. И, наконец, на сумматоре

22 производится сложение содержимого регистров 20 и 21. Результат сложения, являющийся 1 +1- проверочным символом, записывается на регистр

23 по сигналу с выхода 37 блока 3.

В каждом цикле работы устройства на элементе И 27 производится анализ о 35 очередного символа. Если анализируемый символ равен "1111" (), то в блок 3 управления элементы ЗАПРЕТ 26 запрещают выдачу сигналов с выходов

32-34 блока 3, при,этом обнуляется регистр 11.

Начиная с 2-ro цикла и до конца

16-го цикла по сигналу с выхода 38 блока 3 (фиг. 5Д производится вы4S дача информационных символов с пер;вого выхода сдвигового регистра 1 через основной элемент И 2 и элемент ИЛИ 7 на выход 10 устройства. В 17-м цикле по сигналу с выхода 39 блока

3 (фиг. 5к) аналогично производится выдача первого проверочного символа, в 18-м цикле — второго проверочного символа и т.д. по сигналу с выхода

40 блока 3 (фиг. 5 ) четырнадцатого проверочного символа. Начало выдачи тринадцатого проверочного символа совпадает с началом обработки следующего блока информации.

Таким образом, представление информации в виде показателей степени примитивного элемента с поля GF(2 ), являющегося корнем неприводимого многочлена степени m, дает возможность свести получение проверочных символов в операциям сложение и вычитание, что позволяет повысить надежность устройства и его быстродействие, Формула изобретения

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

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

2t-й, первые, вторые и третьи управ" ляющие входы формирователей последующего проверочного символа соответственно объединены и подключены к шес1275782 тому, седьмому и восьмому выходам блока управления, выходы которого с девятого по (2t+9)-й соединены с вторыми входами соответственно основного и дополнительных элементов И с первого по 2t-й, где t — - число ошибок, исправляемых выходным кодом п устройства над полем GF (2 ) .

2. Устройство по п. 1, о т л ич а ю щ- е е с я тем, что формирова- 10 тель первого проверочного символа выполнен на первом, втором и третьем буферных регистрах, вычитателе, сумматоре, преобразователе кода и регистре сдвига, выход последнего разряда которого является первым выходом формирователя первого проверочного символа, информаци: HbIe входы первого буферного регистра являются информационными входами формирователя первого проверочного символа, выходы первого буферного регистра подключены к соответствующим первым входам вычитателя и информационным входам второго буферного регистра, 25 .выходы которого соединены с соответствующими вторыми входами вычитателя, выходы которого, являющиеся вторымй выходами формирователя первого проверочного символа, подключе-, ны к соответствующим первым входам сумматора, выходы которого подключены к соответствующим информационным входам регистра сдвига, выходы-которого соединены с соответствующими входами преобразователя кода, выходы которого подключены к информационным входам третьего буферного регистра, выходы которого соединены с соответствующими вторыми входами сумматора, управляющие входы первого и вто40 рого буферных регистров, регистра сдвига и третьего буферного регистра являются управляющими входами соответственно с первого по четвертый формирователя первого проверочного символа.

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

4. Устройство по п. 1, о т л ич а ю щ:е е с я тем, что блок управления выполнен на дешифраторе, первом элементе И, 2t+1 вторых элементах

И, трех элементах ЗАПРЕТ и счетчике, счетный вход которого объединен с первыми входами вторых элементов И и является тактовым входом блока управления, выходы счетчика подключены к входам дешифратора, первый .и второй выходы которого являются соответствующими выходами блока управления, третий, четвертый и пятый выходы дешифратора соединены с разрешающими входами соответственно первого, второго и третьего элементов

ЗАПРЕТ, запрещающие входы которых объединены и подключены к выходу первого элемента И, входы которого являются информационными входами блока управления, выходы первого, второго и третьего элементов ЗАПРЕТ и шестой, седьмой и восьмой выходы дешифратора являются выходами блока управления соответственно с третьего по восьмой, выходы дешифратора с девятого по (2t+9)-й подключены к вторым входам вторых элементов И соответственно с первого по (2t+1)-й выходы которых являются выходами блока управления соответственно с девятого по (2t+9)-й.

1275782

1275782

7$

ЯФ

s иг. 4

0 цикл /цик// 2 цикл 8цикл /5 цикл /б ци/м /7цикл 20цик//

/ // 5 д У /7 /У /0 57 б00/ б//65 00 //7 20

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

Редактор А. Шандор Техред Л.Сердокс/ва Корректор А.Тяско

Заказ .6582/58 Тираж 816 Подписное

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

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

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