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

4

О)

ьо

со

42)

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

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

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

Устройство для кодирования содержит (фиг. 1) сдвиговый регистр 1 длиной 2

разрядов (2 -длина блока

т-разрядных входных символов), формир

ватель 2 первого проверочного символа, первый (21-1)-й формирователи 3 последующего проверочного символа (t - число ошибок, исправляемых выходньм степенным кодом над полем GF ()), элемент 4 ИЛИ и блок 5 управления. На фиг. 1 обозначены информационный и тактовый входы 6 и 7.

Формирователь 2 первого проверочного символа содержит (фиг. 2) первый - четвертый буферные регистры 8-П, вычитатель 12 по модулю ( преобразователь 13 кода и сумматор 14 по модулю (). На фиг. 2 обоз .начены информационные входы.15, первый, -.четвертый управляющие входы 16-19, вход 20 разрешения считывания, первые и второй выходы 21 и 22 Формирователь 3 последующего про верочного символа содержит (фиг. 3) первый - четвертый буферные регистры 23-26, первый и второй сумматоры 27, 28 по модулю (), вычитатель 29 по модулю () и преобразователь 30 кода. На фиг. 3 обозначены первые - третьи информационные в ход 31-33, первый - пятый управляющие входы 34-38, вход 39 разрешения считывания и.выход 40.

Блок 5 управления содержит (фиг. 4) счетчик 41, детпифратор 42 и элементы 43 И, На фиг. 4 обозначены первый (2t + 1)й выходы 44 и первая - третья группы 45-47 выходов.

Преобразователи 13, 30 кода осуществляют . преобразование кода X в код tJp(X), задаваемый выражением

(i I z гдеу примитивный

0

элемент поля GF(2.

На фиг. 5 обозначены сигналы на входах и вькодах блока 5 управления:

а - на тактовом входе 7;

б - на первом выходе 46.1 второй

на первом выходе 45.1 первой

группы

в группы

г -

на втором группы

д - на группы b J;

е выходе 46,2 второй втором выходе 45.2 первой

на третьем группы bj;

ж - на третьем группы b °;

выходе 46,3 второй выходе 45.3 первой

0 рой группы b ;

3 - на четвертом выходе 46.4 вто5

0

5

0

и - на выходах третьей группы 47

к - на пятом выходе 46,5 второй группы b ;

л - на четвертом выходе 45,4 первой группы

м - на первом выходе 44.1 (управляющий вход сдвигового регистра 1)

н - на втором выходе 44.2 (вход 39 разрешения считьгаания формирователя 3,1) b,j

О, п - на (2t - 1)-м и (2t)-M выходах 44 (входы 39 разрешения считывания формирователей 3, (2t - 1) и 3.(2t)) , b,Y

Р - на (2t + 1)-м выходе 44, (2t) (вход 20 разрешения считывания формирователя 2) Ь т.

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

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

m

5

0

5

нию,

т-разрядных символов в каждом, являющихся показателями степени примитивного элемента rfeGF() - корня неприводимого многочлена f(X) степени m. Обозначим информационные символы K.(i О,.,., .1), проверочные символы, формируемые устройством для кодирования, - Ko(g О,,,,, 2t - 1, где t число ошибок, исправляемых кодовым словом). Тогда j первьй проверочный символ (К в) определяется так

/

Л.

®,...,9с

«-

(1)

. 1462494 ,

а последуюпще проверочные символы1:01 234567- номера по(К, g- 0) по формуламзиций-

К ,: 7 2 1 6 7 7 О 7 - символы

с последовательности.

.

В таблице элементу О поля GF(2) -XiM-f ,w/ j( соотйетствует элемент 7(111), Обоэ- « 09 01 ©..,©0 ® ()

лет

начйм его знаком со , следовательно,

,©/ ,W

где 63 и Ш - знаки суммирования в пле GF (2), а сложение (+) и умножение (.) осуществляется по модулю .

Формирование первого проверочного символа (Ко) будем производить последовательно следующим образом. Обозначим сумму первых двух членов формулы (l), тогда

, где

а операция вычитания (-) производится по модулю .

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

к; К,.+ L/(K,.,- к,), (3) . и

К, К,+и.(К;,-К.) (4) В таблице приведены значения функции M-CZ) для поля GF (2), при- митнвный элемент которого является корнем неприводимого многочлена tСХ) X + X + 1, а также значения

и я ,

В таблице элементу О поля GF(2) соотйетствует элемент 7(111), Обоэ

начйм его знаком со , следовательно,

. (6)

Этот элемент не принадлежит кольцу по модулю 1 (по модулю 7 з на- тем примере), так как, например 171, 0.

Из (6) следует свойство этого элемента

со + а со ,

где а - любой элемент кольца. Действительно

/00 ±0

а -е

О «of

Id

О о/

25

30

Однако, например, 13+417-0, а не 00 ,

В соответствии с формулой (2): к; 2 + if(cc- 2) - 2. Далее, в соответствии с формулой (3)

к;

1 + cf(2 - I) - 4.

Аналогично

K j 6 +1(4 - 6)

3.

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

45

К ,. + ч-СЗ -«) с,(3), К О + If (3 - 0) 1,

К

к: -со) 00(1).

лев К при g О производится аналогично формированию первого проверочного символа. При этом

к; К,+ g + ,(к„- g),

К; к,.+ gi+ ., - К;- g.). (5)

Kg к,+ V(K;., - к,)

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

55 следует пауза для заполнения ее

В качестве примера найдем послед-проверочными символами. Перед начаний проверочный символ К последова-лом работы регистры 10 и 26 устанавтельности с элементами из кольцаливаются в « (единицы во всех m

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

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

по модулю 1 , m 3:

разрядах).

35

К

- + Ц7(3 -со) ех(3)

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

45

К ,. + ч-СЗ -«) с,(3), К О + If (3 - 0) 1,

К

к: -со) 00(1).

55 следует пауза для заполнения ее

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

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

ливаются в

разрядах).

За первыми m тактами следует нулевой цикл, в течение которого по сигналам Ь заполняются первые m разрядов сдвигового регистра 1„ Затем следует первый цикл (т + I, . .., ,2т такты) , в течение которого по сигналам Ъ | в каждом формирователе 3,j производится запись на регистры 23 первого символа информации К сложение его с нулем, поступающим на входы 33, на сумматоре 27, так как в первом цикле i О (см. формулы 5) и затем запись- результата на регистр 24 по сигналам Ь Одновременно в формирователе 2 по сигналу Ь° производится запись К на регистр 8, на вычитателе 12 - вьгчи- тание из содержимого регистра 10 (со) содержимого регистра 8 (К); результат (or,) поступает на преобразователь 13 кода, далее иа сумматоре 14 производится сложение О (выход преобразователя 13) с содержимым -регистра 8 (К) и запись результата (Кд) на регистр 9 по сигна- ЛУ ъ Дзлее п каждом формировате- ,ле 3,j на вычитателе 29 осуществля- : ется вычитание нз содержимого регистра 26 сЪдержимого регистра 24, преобразование результата на преобразователе 30, сложение с содер- ;жимым регистра 24 на сумматоре 28 и I запись результата па регистр 25 по ; сигналу Ь, а на первом формировате- :ле перепись К с регистра 9 на ре- ;гистр 10 по сигналу Ь. : К концу первого цикла сдвиговый I регистр 1 полностью заполняется и, начиная со второго цикла, через элемент 4 ИЛИ информация с последовательного выхода сдвигового регистра i поступает на выход устройства.

Второй цикл (2т + 1,..., 3т такты) аналогичен первому циклу для формирователя 2. R формирователях 3.J по сигналам Ь, производится Запись на регистр 23 второго символа К , сложение его с величиной g (см. формулу 5), поступающей с блока З управления на входы 33 (сигналы Ь) и далее на сз мматоры 27; результат записывается на регистр 24 по сигналу bJ. Одновременно по сигналу b содержимое регистра 25 пе- реписывэе тся на регистр 26, Далее на вычитателе 29 осуществляется вычитание из содержимого регистра 26 (К ), содердимого регистра 24 (К), преоб4624946

разование результата на преобразователе 30 и сложение с содержимым регистра 24 (К,) на сумматоре 28 с J записью суммы К ,+ (-/( К,) на регистр 25 по сигналам Ъi,

Циклы с третьего по (2т - 1)-й аналогичны второму, причем в (2т-1)-м цикле в последующих формирователях 10 3.1,... J 3(2t - 1) на регистрах 25 будут находиться К без KQ (2).

К (2ш)-м цикле формирователь 2 работает аналогично второму циклу, причем далее производится передача

J5 сформированного в формирователе 2 первого проверочного символа К с регистра 9 на входы 32 формирователей 3. ,..., 3,(2t - 1) и запись на регистры 24 по сигналу Ь,.. Затем в

20 (2т + 1)-м цикле по сигналам Ъ содержимое регистра 25 переписывается на регистры 26 формирователей 3,1, ..., 3.(2t - 1). Одновременно по сигналу Ь первый проверочный сим25 вол Kjj переписывается с регистра 9 на регистр 11 формирователя 2. Далее на вычитателях 29 формирователей 3 ,1,. ..,3,(2t - 1) производится вычитание первого проверочного симво

30 содержимого регистров 26

(К без KQ)S преобразование результатов на преобразователях 30 и сложение с содержимым регистров 24 (К) на вторых сумматорах 28 с записью результатов (К, .g7 0) на регистры 25 по сигналам bj.

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

В остальных 2t - 1 циклах 45 (с ( 3)-го по ( 2t + 1)-й

цикл обработки текущего блока информации, кулевой и первьй циклы обработки следующего блока информации) производится последовательная вьща ча проверочных символов К,,..., К с регистра 25 формирователей 3,2,,tV ...j3.(2c - 1) по сигналам Ъ,,,.., Ь соответственно и первого проверочного символа Кр с регистра 11 по сигналу Ь , через элемент 4 ИЛИ на выход устройства. Начало вьщачи первого проверочного символа К совпадает с началом обработки следующего блока информации.

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

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

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

.

10

20

25

5

0

5

соответственно первого - (2t - 1)-го формирователей последующего.проверочного символа и формирователя первого проверочного символа,

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

30

35

40

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

10

Q 0 5

5

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

А. Устройство по п. 1, о т л и - чающееся тем, что блок управления содержит дешифратор, первый - (2t + 1)-й элементы И и счетчик, вход которого объединен с первыми входами всех-элементов И и является входом блока, выходы счетчика соединены с входами дешифратора, первый - (2t -f 1)й выходы которого подключены к вторьы входам соответственно первого - (2t 4- 1)-го элементов И, выходы которого являются соответственно первым - (2t + 1)-м выходами блока, первая, вторая и третья группы выходов дешифратора являются одноименными группами выходов блока.

J2 33 Jf

5r «5.

К.Ь «;СГ |§ 1,

t

i

ь|

v§ Е

«м

ссз:

:1ЛЗЛ

J.

)i6«n3 ee;t

% О e c

, «

ЭЕЕШагсз

% О e c