Устройство для кодирования линейных полиномиальных кодов Советский патент 1992 года по МПК H03M13/02 

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

Цель изобретения - упрощение устройства.

Функциональная схема устройства приведена на чертеже.

Устройство содержит регистры 1 памяти, блоки 2 сумматоров по модулю q, блоки 3 умножения и блок Ч коммутаторов. На чертеже обозначены первые 5 и вторые 6 информационные входы, управляющие входы 7 и выходы 8 устройства.

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

Задача кодирования заключается в том, чтобы по заданной порции входных информационных символов по заданному закону, называемому кодом, построить большую (на заданное количество символов) порцию выходных

данных-символов. Как правило на практике используются коды, выходные слова которых полностью содержат все информационные символы и заданное кодом количество проверочных символов, формируемых по кодовому правилу из информационных. Кодирование по таким кодам сводится к генерации проверочных символов и присоединении их к информационным. При кодировании по полиномиальному коду проверочные символы должны быть сгенерированы так, чтобы многочлен кодового слова W(x) делился на многочлен G(x),, т.е.

( + ...+ Wn, )modG(x)0,

где п - количество символов в кодовом слове ()i t qm-1 - максимальная длина

W0 , W , ... Мц., символы кодового

W

оо со

00

слова (все)j

m - число разрядов символа кодового слова;

q - число различных значений одного разряда символа .. (как правило, используют двоичные коды, ,8; )1, qm- число различных значений од-

ного символа Ј п-р)Ч - число различных кодовых

слов , р - число проверочных символов

в коде.

Для описания работы устройства елесообразно ввести многочлены (х) W0 + W,x + ...+ WeH-xe j

(x) We+p + Vt+p + {, x +..., де Wj,

w

&H

, ...

,w

е+ри

we+p.+

™ П-1

проверочные символы кодового слова 5

информа ционные символы, старшее полуслово ;

0, W, Wg

информационные символы, младшее полуслово,

которые назовем многочленами соответственно младшего и старшего информационного полуслова, и многочлен

t-e-i

К(х) (х

modG(х)) х.

Вначале регистры 1 обнуляются.: Это можно произвести двумя способами: подав активный уровень на объединенные управляющие входы сброса всех регистров 1 памяти или записав во все регистры 1 нули через информационные входы. Коммутаторы блока и, служащие для отключения обратной связи, замкнуты. На входы 5 и 6 по одному параллельно, начиная с коэффициентов при наивысшей степени и кончая свободными членами, подаются коэффициенты многочленов старшего и младшего информационных полуслов соответственно. За один рабочий такт на входы 5 и 6 подается по одному коэффициенту соответствующего многочлена. На входы 5 подается многочлен С(х), а на входы 6 - многочлен А(х). Символы на входах 5 и 6 подаются параллельными парами. Для определения прове

10

:13384

рочных символов устройству необходимо совершить U max(ll, n-1-p) рабочих тактов. На первом такте на входы 5 и 6 подается по коэффициенту от многочленов А(х) и С(х) при степени U-1 еоответстпенно. Последней в устройство поступает пара символов Wa , Wg +p-.- каждый на свои входы.

Опишем один такт работы устройства. На входы 5 поступает символ С ,, на входы 6 - символ Aj. Блоки 3.(р+1) - З.(2р) умножения осуществляют умножение Л на коэффициенты

15 многочлена К(х), и на третьих вхо- .дах блоков 2.2 - 2.р сумматоров формируются соответствующие произведения. На третьих входах блока 2.р сумматоров появляется символ произ20 ведения, равный A;-Kp. Этот символ складывается по модулю q с символом CJ, поступающим на входы 5, и с содержимым последнего регистра 1.р памяти. (Это сложение произво25 дит блок 2.р сумматоров.). Сумма с выхода блока 2.р поступает через открытые коммутаторы блока k на входы блоков 3.1-З.Р умножения. Блоки 3.1 - З.Р формируют произведе30 кие этой суммы на коэффициенты -ge, -gj,.. .,-g p( образующего многочлена кода со знаком -. Соответствующие произведения поступают на вторые входы блоков 2.1 - 2.(р-1)

35 сумматоров (кроме произведения на 8о Формируемого блоком 3.1 умножения, которое поступает на вход регистра 1.1). На первые входы каждого блока 2.1 - 2.(р-1) сумматоров

4Q поступает символ, находящийся в предыдущем регистре 1 памяти. Три символа, сформировавшиеся на трех различных входах каждого из блоков 2.1 - 2.(р-1), складываются в нем по

45 модулю.q и сумма подается на входы следующего за ним регистра 1 памяти. Затем на управляющие входы 7 подается сигнал разрешения записи во все регистры 1 памяти, и символы, находившиеся на входах регистров 1.1- 1.р, записываются в них. На этом очередной такт работы устройства кодирования завершается.

После U тактов работы в регистрах t находятся проверочные символы. Коммутаторы блока 4 размыкаются. Символы, находящиеся в регистрах 1.1 - 1.р, по одному считываются на выходы 8. На этом кодирование

50

55

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

В случае кода недвоичной разрядности (q 2) устройство выдает проверочные символы с противоположным знаком. Для недвоичного кода можно

торов по модулю q уменьшено на один кроме того, все блоки 2 имеют по тр группы входов.

Ф

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

Устройство для кодирования линейных полиномиальных кодов, содерпоставить на выходе устройства инвер- JQ жащее первый - р-й регистры памяти тор в поле GF(q).

Анализ работы устройства показывает, нием

А-1

15

что оно описывается соо.тношеwe

+ W

е+с

х +... + W

,f

-

Ј+р-Г

(x).K(x)+C(x)(x),

характеризующим следующий метод кодирования: устройство генерирует проверочные символы в регистрах 1.1- 1.р как остаток от деления на порождающий многочлен G(x) суммы произведений многочленов младшего и старшего информационных полуслов на К(х) и хР соответственно.

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

V 1 +max(deg A(x)j degC(x);

20

25

30

(р - число проверочных символов выходного кода, заданного в поле GF(qm где q - значность одного разряда символа выходного кода , m - число разрядов символа выходного кода-), управляющие входы которых соответственно объединены и являются управляющими входами устройства, причем выходы первого - (p-l)-ro регистров памяти соединены с первыми входами одноименных блоков сумматоров по модулю q, выходы кото рых подключены к информационным вхо дам соответственно второго - р-го регистров памяти, выходы р-го регистра памяти соединены с первыми входами р-го блока сумматоров по модулю q и являются выходами устройства, вторые входы р-го блока сумматоров по модулю q являются первыми информационными входами устройства, выходы р-го блока сумматоров по модулю q подключены к соответствующим входам блока коммутаторов, выходы которого соединены с входами первого - р-го блоков умножения, выходы второго - р-го блоков умножения подключены к вторым входам соответственно первого - (p-l)-ro блоков сумматоров по модулю q, (р+1)-й - 2р-й блоки умножения, входы которых соответственно объединены и являются вторыми информационными входами устройства, выходы

35

degA(x) 2 - degC(x) -2-1 .

1

Н:Е

2

степени этих

равны

degA(x)

п-Ј 2

1J

DIE 2

1

degC(x)

Следовательно, искомое количество тактов V -

По сравнению с 2J в данном устройстве количество блоков 2 сумматоров по модулю q уменьшено на один, кроме того, все блоки 2 имеют по три группы входов.

Ф

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

р- JQ жащее первый - р-й регистры памяти

15

- )

20

25

30

(р - число проверочных символов выходного кода, заданного в поле GF(qm), где q - значность одного разряда символа выходного кода , m - число разрядов символа выходного кода-), управляющие входы которых соответственно объединены и являются управляющими входами устройства, причем выходы первого - (p-l)-ro регистров памяти соединены с первыми входами одноименных блоков сумматоров по модулю q, выходы которых подключены к информационным входам соответственно второго - р-го регистров памяти, выходы р-го регистра памяти соединены с первыми входами р-го блока сумматоров по модулю q и являются выходами устройства, вторые входы р-го блока сумматоров по модулю q являются первыми информационными входами устройства, выходы р-го блока сумматоров по модулю q подключены к соответствующим входам блока коммутаторов, выходы которого соединены с входами первого - р-го блоков умножения, выходы второго - р-го блоков умножения подключены к вторым входам соответственно первого - (p-l)-ro блоков сумматоров по модулю q, (р+1)-й - 2р-й блоки умножения, входы которых соответственно объединены и являются вторыми информационными входами устройства, выходы

45 (р+1)го - (2р-1)-го блоков умножения подключены к третьим входам соответственно первого -. (p-l)-ro блоков сумматоров по модулю q, отличающееся тем, что,

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

35

40

5 „

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