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

 

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

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

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

РЕСГ1УБЛИН

1бд,1 Н 03 М 13/02

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

Н ABTOPCKOMY СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 4310932/24-24 (22) 21.08.87 (46) 28.02.89. Бюл. М 8

{72) A.È.Êàðïóõèí (53) 681.325(088.8) (56) Питерсон У., Уэлдон Э. Коды,исправляющие ошибки, — 1 1.: Мир, 1976 с. 134-135, Францис Т.А., Янбых Г.Ф. Избыточность в электронных дискретных устройствах, Л.: Энергия, 1969, с. 227-228, Авторское свидетельство СССР й, 1275782, кл. Н 03 М 13/02, 1985.

ÄÄSUÄÄ 1462494 А1

{54) УСТРОЙСТВО ДЛЯ КОДИРОВАНИЯ

{57) Изобретение относится к вычислительной технике и технике. связи, .может использоваться в- системах передачи и хранения цифровой информации и позволяет повысить быстродействие. Устройство содержит сдвиговый регистр 1, формирователь 2 первого проверочного символа, формирователи 3 последующих проволочных символов, элемент ИЛИ 4 и блок 5 управления. Поставленная цель достигается благодаря реализации в устройстве нового алгоритма обработки, позволяющего вдвое увеличить информационную часть передаваемого кодового слова. 3 s.ï, ф-лы, 5 ил.

1462494

45

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

Цель изобретения — повышение быстродействия.

На фиг. 1 показана блок-схема устройства для кодирования. На 10

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

m-разрядных входных символов), формиро- 2О ватель 2 первого проверочного символа, первый (2t-1)-й формирователи 3 последующего проверочного символа (t — число ошибок, исправляемых выходным степенным кодом над полем

GF (2 )), элемент 4 И11И и блок 5 управления. На фиг. 1 обозначены информационный и тактовый входы 6 и 7.

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

8-11, вычитатель 12 по модулю (2 -1), преобразователь 13 кода и сумматор

14 по модулю (2 -1), На фиг, 2 обоз.начены информационные входы .15, первый,-.четвертый управляющие входы

16-19, вход 20 разрешения считывания, первые и второй выходы 21 и 22.

Формирователь 3 последующего про" 4О верочного символа содержит (фиг. 3) первый - четвертый буферные регистры 23-26 первый и второй сумматоры

Ю О

27 28 по модулю (2 -1), вычитатель

YA

29 по модулю (2 -!) и преобразователь 30 кода. На фиг, 3 обозначены

Ъ первые - третьи информационные входы

31-33, первый - пять»й» управляющие входы 34-38, вход 39 разрешения счить»вания и.выход 40.

Блок 5 управления содержит (фиг. 4) счетчик 41 дешифратор 42 и элементы 43 И. На фиг. 4 обозначены первый (2t + 1)-й выходы 44 и первая - третья группы 45-47 выхо55 дов, Преобразователи 13, 30 кода осуществляют.преобразование кода Х в код Ц(Х), задаваемый выражением — +, Где « — примитивный элемент поля GF(2 ).

На фиг. 5 обозначены сигналы на входах и выходах блока 5 управления: а — на тактовом входе 7; б — на первом выходе 46.1 второй группы b,; в — на первом выходе 45.1 первой группы Ь ; г — на втором выходе 46 ° 2 второй группы b>

7 д - на втором выходе 45.2 первой

0 группы Ъ 1, е — на третьем выходе 46.3 второй группы b ; ж — на третьем выходе 45.3 первой

0 ° группы b з — на четвертом выходе 46,4 втоРой группы Ь»1 и — на выходах третьей группы 47 ч к - на пятом выходе 46,5 второй группы b л — на четвертом выходе 45,4 первой групчы Ь, м — на первом выходе 44.1 (управляющий вход сдвигового регистра 1) Ь„ н — на втором выходе 44,2 (вход

39 разрешения считывания формирователя 3.1) Ь 11

О, п — на (26 — 1)-м и (2t)-м выходах 44 (входы 39 разрешения считывания формирователей 3, (2t — 1) и 3. (2t) ) Ъ, Ь» р " на (2t + 1)-м выходе 44 ° (2t) (вход 20 разрешения считываI ния формиро7»ателя 2) Ъ 1.

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

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

m-разрядных символов в каждом, являющихся показателями степени примитивного элемента c(GF(2 ) - корня неприводимого многочлена f(Х) степени m, Обозначим информационные символы К,.(i = О,..., 2 - .1), проверочные символы, формируемые устройством для кодирования, - K>(g О,...»

2t — 1, где t - число ошйбок, исправляемых кодовым словом). Тогда первый проверочный символ (К,) опре" деляется так

1 Р-1 9 i» 0 +(1 р Я g((») 1462494

О. (6) в+а о, Аналогично а последующие проверочные символы (К,), g > О) по формулам

hl к+

2 Я- „; 3 ®, "о

1 0

К, К,+ ) X;++ I< ("-2) (О В...О (О 8("е "o р) ,10 где ц и .в - знаки суммирования в по" ле GF (2 ), а сложение (+) и умножение (.) осуществляется по модулю

2 -1, Формирование первого проверочно15 го символа (К ) будем производить последовательно следующим образом.

Обозначим сумму первых двух членов формулы (1) с!, тогда к, к, к, кi М(к,-< 1 = с(Ю d = с

20 где с = I O+ +c(Ч(1 а операция вычитания {-) производится по модулю 2 -1.

В общем случае

К,. = К,.+ Ч(К,,- К.,), (3) .

5 и

К = K.,+ Ч(К,) (4)

В таблице приведены значения функции М(Е) для поля GF (2 ), при» митивный элемент d которого является корнем неприводимого многочлена

f(X) = Х + Х + I, а также значения

Z и,(2, 001 000 11!

010 001 011

100 010 ) 10

011 01) 001

110 )00 )OI

))1 101 100

I 0 I I I O 010

000 111 000

Формирование проверочных символов К> при g ) 0 производится аналогично формированию первого прове45 рочного символа. При этом

К = K, g + +q(K, — K,- g)

= К,+ g;+ Ч(к;, — К;- g;). (5)

+ Ч(К К ) 5()

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

К, 55

В качестве примера найдем последний проверочный символ К последовательности с элементами из кольца по модулю 2"- I, m = 3:

О 1 2 3 4 5 6 7 - номера позиций;

Ф

К,: 7 2 1 & 7 7 О 7 - символы последовательности.

В таблице элементу 0 поля GF(23) соответствует элемент 7(III) ° Обозначим его знаком, следовательно, Этот элемент не принадлежит кольцу по модулю 2 - 1 (по модулю 7 в на» шем примере), так как, например (7(1 = О.

Из (6) следует свойство этого элемента где а - любой элемент кольца, Действительно

Однако, например, (3 + 4(1 О, а не

В соответствии с формулой (2):

- 2+M(- 2) 2 °

Далее, в соответствии с формулой (3) К + Ч(2 - 1) 4 °

К 6 +Ч(4 — 6) 3, К + q(3 - ) (3)

Ф

Здесь используется то обстоятельство, что К,, равное, не переда. ется на второй буферный регистр 9 и таким образом на регистрах 9 и !О сохраняется предыдущее значение (в скобках после знака ).

Аналогично

К =+ ч(3 - о) = (3)

К =О+р(3-О) -1, 6

К - К = +q(I — ) - (l)

1 о

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

На вход 6 устройства поступают блоки информации по 2 m разрядов в сопровождении тактовых имПульсов

Ъ, затем 2t циклов (2t m тактов) следует пауза для заполнения ее проверочными символами. Перед началом работы регистры 10 и 26 устанав" ливаются в с (единицы во всех m разрядах).

1462494

За первыми m тактами следует нулевой цикл, в течение которого по сигналам Ь заполняются первые m разрядов сдвигового регистра l. Затем следует первый цикл (m + 1,...,, 2m такты), в течение которого по 1 сигналам h > в каждом формирователе

З.j производится запись на регист-" ры 23 первого символа информации К сложение его с нулем, поступающим на входы 33, на сумматоре 27, так, как в первом цикле i = 0 (см. форму, лы 5) и затем запись результата на регистр 24 по сигналам Ь . Одноврег менно в формирователе 2 по сигналу о b производится запись !< на регйстр Я, на вычитателе 12 — ньяи, тание из содержимого регистра 10 ! () coZ<:.ржимого регистра Я (К,); . результат (<;) поступает па преобра, зователь 13 кода, далее па суммато, ре 14 производится сложение "0 (выход преобразователя 13) с содер,жимым регистра Я (К ) и запись рео зультата (К ) на регистр 9 по сигнао а лу b >. Далее в каждом формировате,ле 3 .j на вычитателе 29 осуществляется вычитание из содержимого регистра 26 содержимого регистра 24, преобразование результата на пре-образователе 30, сложение с содержимым регистра 24 на сумматоре 28 и запись результата на регистр 25 по сигналу b ) а на первом формировате 1 ле перепись К с регистра. 9 на регистр !О по сигналу Ь„, I(концу первого цикла сдвиговый регистр 1 полностью заполняется и, начиная со второго цикла, через элемент 4 ИЛИ информация с последовательного выхода сдвигового регистра

1 поступает на выход устройства.

Второй цикл (2m + l,..., 3m такты) аналогичен первому циклу для формирователя 2. В формирователях

З.j по сигналам Ь „ производится эа1 пись на регистр 23 второго символа К,, слоя<ение его с величиной g (см, формулу 5), поступающей с блока 5 управления на входы 33 (сигнаТп лы Ь,,) и далее на сумматоры 27; результат записывается на регистр 24 по сигналу b- . Одновременно по сиг) налу Ь 1 содержимое регистра 25 переписывается на регистр 26, Далее на вычитателе 29 осуществляется вычитание иэ содеря<имаго регистра 26 (К,), содердимого регистра 24 (К,), преоб40

5

3S разование результата на преобразователе 30 и сложение с содержимым регистра 24 (К„) на сумматоре 28 с записью суммы К,+ y(K — К,) на регистр 25 по сигналам Ь i

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

3.1,..., 3(2t — 1) на регистрах 25 будут находиться К > беэ К, (2) .

В (2m)-м цикле формирователь 2 работает аналогично второму циклу, причем далее производится передача сформированного в формирователе 2 первого проверочного символа К, с регистра 9 на входы 32 формирователей 3.1,..., 3.(2t — 1) и запись на регистры 24 по сигналу Ь . Затем в (2m + l)-м цикле по сигналам Ь, содержимое регистра 25 переписывается на регистры 26 формирователей 3,1, 3.(2t — 1). Одновременно по сигналу Ь первый проверочный символ К, переписывается с регистра 9 на регистр 11 формирователя 2. Далее на вычитателях 29 формирователей

3 à 1у,° ° е, 3 е, 2t — 1 ) производится Вы читание первого проверочного символа I<, из содержимого регистров 26 (К беэ Кр) ., преобразование резуль" татов на преобразователях 30 и сложение с содержимым регистров 24 (К, ) на вторых сумматорах 28 с записью результатов (К р р, > О) на регистры

25 ло сигналам Ь .

В следующем (2 + 2)-м цикле по сигналам Ь прсизводится выдача вто2 рого проверочного символа К с регистра 25 формирователя 3. 1 через эле" мент 4 ИЛИ на выход устройства.

В остальных 2t — 1 циклах (с (2 + 3) -го по (2 + 2t + I)-й цикл обработки текущего блока информации, нулевой и первый циклы обработки сл"дующего блока информации) производится последовательная выдача проверочных символов К,... К еес резистра 25 формирователей 3.2,... ...,3.(2t — l) по сигналам Ь 1,..., b, соответственно и первого прове it рочного символа Кр с регистра 11 по

< сигналу b 1 через элемент 4 ИЛИ на выход устройства. Начало выдачи первого проверочного символа К, совпадает с началом обработки следующего блока информации, 1462494

Устройство для кодирования позволяет по сравнению с прототипом увеличить скорость передачи информа-. ции (отношение числа информационных разрядов к числу разрядов кодового слова) путем увеличения информационной части до 2 m-разрядных символов. l0

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

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

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

2 — 1, преобразователь кода и сумматор по модулю 2 - 1, информационные входы первого буферного регистра являются информационными входами формирователя, информационные выходы первого буферного регистра подключены к IIepBblM входам сумматора по модулю 2 — 1 и вычитателя по мо ъ дулю 2 — 1, выходы которого соединеН1 ны через преобразователь кода со вторыми входами сумматора по модулю ъ

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

2 - 1, управляющий вход первого, второй управляющий вход второго и первый управляющий вход четвертого и управляющий вход третьего буферных регистров являются соответственно первым — четвертым управляющими вхо" дами блока, второй управляющий вход и выход четвертого буферного регистра являются соответственно входом разрешения считывания и вторым выходом формирователя.

3„ Устройство по и. 1, о т л ич а ю щ е е с я тем, что формирователь проверочного символа содержит первый - четвертый буферные регистры, первый и второй сумматоры по модулю 2 "- 1, вычитатель по модулю

2 - 1 и преобразователь кода, инфор-, 1ъ мационные входы первого буферного регистра являются первыми информационными входами формирователя, выходы первого буферного регистра соединены с первыми входами первого сумматора

П1 по модулю 2 — 1, выходы которого . подключены к первым информационньи входам второго буферного регистра, 1462494

32 ЗЗ

l 462494

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

Техред М.Ходанич Корректор Н. Король

Редактор А. Долинич

Заказ 736/56 Тираж 879 Подписное

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

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

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