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

00

о 00

Изобретение относится к Е ЫЧИСЛИ- тельно технике и может быть использовано в системах передачи информации.

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

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

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

Первый и второй умножители 1 и 2 могут быть выполнены (фиг. 2 и 3) н сумматорах 18-29 и 30-40 по модулю Два.

В основе работы устройства для кодирования лежит следующее.

В ко 1овых комбинациях кода Рида- Соломона имеется К информационных и U-K проверочных символов, каждый из которьк содержит т-двоичных символов, где п - кодовой комбинации (блока) . Символы являются элементами ноля Галуа GF (2 ). Пусть

f(X) - полином, к коэффициентов кот

лг

ptoro при cлaгae ьrx, содержащих X Х , ..., , выбраны информациоными сиг-1волами, а коэффициенты при слагаемых X со степенями, меньшими П-К, равны 0. Такому многочлену соответствует вектор, первые К компонент которого - информационные символы, а последние п-К компонент равны О.

В соответствии с алгоритмом делекия Евклида

f(x) g(x).g(x) + r(x), (1)

т де g(x) - порождающий многочлен

кода; g(x) - полином информационных

символов; г(х) - остаток от деления f(x)

на g(x).

Степень многочлена г(х) меньше чем п-К, а к(х) - равна п-К.

Кодовый блок может быть найден как результат умножения полинома степени не выше К-1, коэффициентами которого являются информационные С11мволы, на порождающий многочлен g(x). И признаком кодового блока является деление без остатка полинома g(x) g(x) на g(x). Признаком обна- ружения ошибок в кодовом блоке является возникновение остатка при делении.

Выражение (1) можно записать в виде

f(x) + г(х) g(x).g(x).

(2)

0

5

При двоичных сигналах вычитание можно заменить сложением.

Поскольку первая часть выражения (2) - кодовый блок, то и левая часть также делится без остатка на g(x). Следовательно, для кодирования можно использовать два способа в соответс- вии с левой и правой частью выражения (2). Кодирование с помощью левой части удобнее, поскольку информационные символы получают в неизменном виде. В этом случае К коэффициентов

0 информационных символов К(Х) необхо,, п-к димо умножить на X , в результате

чего получают f(X), младшие п-К разрядов которого равны О и с которыми необходимо сложить г(Х) - остаток от деления К(К) f(X) на g(X) .

5

Кодовый блок по выражению f(X) +

+ г(Х) можно получить с помощью регистра сдвига с обратными связями, содержащего п-К ячеек памяти (регист0 ров). Регистр сдвига строится на основе порождающего многочлена g(X). Для кодов Рида-Соломона (PC) над полем Галуа GF(q) с длиной п q-1 порождающий полином находится из вы-

5 ражения

g(x) (х -сС)(х - Л)...(х - Л-1

-ОС

),

(3)

где ct - примитивный корень поля Галуа GF(q,

d - кодовое расстояние.

При сложении по модулю два в поле Галуа GF(2) выражение (3) можно переписать в виде

g(x) (х +о6)(х + йб ) ...(х+ г-, где m - разрядность символов в поле Галуа.

3 П908014

Наибольшее распространение полу-При исправлении однократной ошибчили поля Галуа GF(2) (та 8), чтоки в поле GF(2 ), элементы которого

соответствует разрядности байта ин-образуются с помойные примитивного формации. 5 полинома F(X) К + х + X + X +1,

порождающий многочлен может иметь

Сущностью алгоритма кодирования, следующих видов

реализуемого в предлагаемом устрой- N, - ) (х ) к +

стве, является выбор для порождаю-

щего полинома g(x) таких пар сомно-+ ( ti +л.)х+ х -1-х

жителей (X -ь Л ) (Х + otM , сумма ко- iss. эффициентов в которых при переменной

X становится равной единице, где - (х + it ) (х + i ) +

m - разрядносГть элементов поля ..2

GF(2), п - длина кода, К - число+ ( tL + eL )х + d. х + х -i-li . информационных элементов в коде, А- Элементы поля GF(2) (десятичные примитивный элемент поля Галуа GF(2) . числа являются степенью Л):

,-.,1

0-1111111121 -10101101

1-1000000022 -00111000

2-0100000023 -11000011

3-0001011124 -11100010

4-0010000025 -00101010

5-1110011026 -01101100

6-1000101127 -01000001

7-1110010028 -00111001

8-0001000029 -11101101

9-00110100.30 -00101111

10- О 1 1 1 О О 1 131 - 1 1 1 О О О 1 1

11-0111000032 -00000100

12-1100010133 -10100001

13-1101100034 -10001000

14-0111001035 -01010001

15-0101111036 -00001101

16-0000100037 -10011110

17-0001000138 -01011111

18-0001101039 -00100110

19 1011111040 -11011100

20- 1 О 1 1 1 О О 141 - 1 1 О 1 О О 1 1

- 1 1 О 1 О 1 1 О

- О 1 О 1 1 О О 1

- О О О 1 1 1 О О

- 1 О О О .0 1 О О

- 1 1 1 О О О О 1

- 1 О О 1 1 1 1 1

- О 1 1 1 О О О 1

- 11101011

- О О О 1 О 1 О 1

- 1 О 1 1 1 О 1 1

- О О 1 1 О 1 1 О

- 1 1 1 О 1 О О О

-10100000

- 1 О 1 О О 1 1 О

- 1 О О 1 1 1 О О

-11000-100

- 1 1 1 1 О 1 1 О

- 1 О 1 1 1 1 1 1

- 1 О О 1 О 1 1 1

- О 1 1 О О О О О

- 1 1 1 1 О О О 1

- 1 О 1 О 1 О 1 1

-00000010

- 1 О О 1 1 О 1 1

- 1 1 О 1 О О О О

- О 1 1 О О О 1 1

-01000100

- 1 О 1 1 О 1 1 О

- 1 О 1 О 1 .0 О О

13908016

71- 1 О 1 1 О 1 1 1

72- 1 О О О О 1 1 О

73- О 1 1 1 1 О 1 О

74- О 1 О О 1 1 1 1

75- О О О 1 О О 1 О

76- 1 О 1 О 1 1 1 1

77- 1 О 1 О О О 1 1

78- О О О 1 О О 1 1

79- 1 О О О О О О 1

80- О 1 1 О 1 1 1 О

81- 1 1 О 1 1 О 1 О

82- 1 1 1 О 1 О О 1

83- 1 О О О 1 1 1 О

84- О 1 1 О 1 О 1 1

85- О 1 О 1 О 1 О 1

86- 1 О 1 О 1 1 О О

87- О О О 1 О 1 1 О

88- О О о О 1 1 1 О

89- О О 1 О 1 О 1 1

90-01000010

91- 1 О О О 1 1 О О

92- 1 1 1 1 О О О О

93- 1 О О d О 1 О 1

94- 1 1 О О 1 1 1 1

95- О 1 О 1 О О 1 О

96- 1 О 1 1 1 О О О ,97- 1 О О 0-0 О 1 1

98- 1 1 1 1 О 1 О 1

99- О О О О 1 О 1 О

71390801 8

- 1 О О О 1 О 1 О1Z9 - О О 1 О 1 1 1 О

- 1 1 О О 1 О 1 О130 - 1 1 О О 1 1 О 1

- 1 1 О 1 1 1 О 1131 - 1 1 О О 1 О О 1 - 1 1 1 1 1 1 О 1132- о 1 1 о 1 о о о

- О О О 1 1 О 1 1133- 1 1 1 О О О О О

- 1 о о 1 о о о о134- 1 О 1 1 О О О 1

- о 1 1 1 о 1 о о135- 1 О 1 1 1 1 О О

- О 1 1 О О 1 О О136- О О 1 О О О 1 О

- О 1 О 1 О О О О137- О 1 1 1 1 1 О 1

- О О 1 О О О 1 1

138- О 1 О 1 1 О 1 1

- О 1 О 1 О О 1 1

139- 1 О О О О 1 1 1

-10010110

140- О 1 О 1 О 1 О О

- О 1 О О 1 1 1 О

141-10000010

- О О 1 1 1 1 О О

142- 1 1 О 1 1 О 1 1 -01100010

- О 1 1 О 1 О 1 О143- 1 1 О О О 1 1 1

-01111011144-01000011

- О 1 1 О О О О 1145- 1 О 1 О О О 1 О

-11011111146-00111101

- О 1 1 О О 1 1 О147- О 1 О О 1 1 О О

- 1 1 О О 1 О 1 1148- 1 О 1 О О 1 1 1

- 1 1 1 1 О О 1 1149- 1 О 1 10010

- О О 1 1 О О О О150- О О О О 1 О О 1

- 1 1 О 1 О О 1 О151- О О 1 1 1 1 1 1

- 1 1 1 1 1 О О О152- 1 1 О 1 О 1 1 1

- 1 О О 1 О 1 О О153- О 1 1 1 О 1 1 1

- 1 1 О 1 О 1 О 1154- 1 1 О 1 О О О 1

- 1 1 1 О 1 1 О О155- О 1 О О 1 1 О 1

-00000001156-10001001

111390801

215- О 1 О О 1 О О 1

216- О О 1 О 1 О О О

217- 1 1 1 1 О 1 1 1

218- 1 О О 1 О О О 1

219- О 1 О 1 1 О 1 О

220- 1 О 1 О 1 О О 1

о

221- 1 О О 1 1 О О 1

222- О 1 О О 1 О 1 1

223- 1 О 1 1 О О 1 1 27.4- О О 1 О О 1 1 1

225- 1 1 1 1 О О 1 О

226- О О О 1 1 1 1 О

227- О О О 1 1 1 1 t

228- О О 1 1 О 1 О 1 229- 1 1 1 1 1 1 О О -1230- О О 1 1 О 1 О 1

231- О 1 О 1 1 1 О 1

232- 1 О 1 1 1 1 О 1

233- О О О О 1 1 О О

234- 1 О 1 1 О О О О

235- 1 О О 1 О О 1 О з представленных данных видно.

+ дв щи

что

«1 , 2

(. + А 1 и flt +

ос 1.

Для исправления двухкратных оши - - ъ. . - т - - -. .

бок целесообразно взять

g(x) g,(x)g,j(x) (х + X +

+ Л )(х + X -ь ) X +

-I- («6 + 1)х + + . Устройство для кодирования, построенное по полиному g{x)

+ (iC +

1 1 1 О 1 1 1 1

1 О 1 1 О 1 О О

О О 1 1 О О 1 1

О 1 1 О О 1 1 1

1 1 1 О О 1 О 1

О О 1 1 1 1 1 О

1 1 1 1 1 О О 1

1 О 1 1 1 О 1 О

О О О 1 1 О О О

О О 1 О О 1 О 1

О 1 1 О 1 О О 1

1 1 О О 1 1 1 О

О 1 1 1 1 1 О О

О 1 1 1 О 1 О 1

О 1 О О 1 О 1 О

1 О О 1 1 1 О 1

1 1 1 О 1 О 1 О

О О 1 1 1 О 1 1

О 1 1 1 О 1 1 О

1 1 1 1 1 1 1 1

0

+ 1)х + fli X , при исправлений двухкратных ошибок, работает следуюЧ щим образом.

Информационные символы,количеств6 которых К п - 4, подаются с входов 13 параллельно на блоки 11 и 12. Во время подачи информационных символов управляющим сигналом Т1 (К тактовых импульсов) открыт блок 4 и по nepBbn t информационным входам - блок 12. В - результате информационные символы подаются на вькоды 17 устройства и в шину обратной связи на входы умножителей 1 и 2. Полином информационных символов К(Х) за счет подачи на

В1.1ХОД регистра умножается на X X , где 4 - число нроверочных символов. В устройстве для кодиропания осуществляется деление К(Х) Х на полином g(x) X + ( frC + 1)х +

сд214

ее X + d . Деление заканчивается как только п-4 информационных символов поданы на входы 13, в результате чего в регистре сдвига, сое- тавленном из буферных регистров 5-8, получен остаток г(Х) г X + г X + + г Х + Гц. Пос.ле этого блоки 4 и 12 по первым информационным входам закрываются, а по вторым открывают- ся управляющим сигналом Т2 на входе 16.Проверочные элементы из регистров 5-8 выводятся вслед за информационными элементами. Таким образом, закодировано сообщение, имеющее длину п байтов.

Умножители 1 и 2 производят умножение на соответствующие постоянные

;21Э 64

элементы поля об и о , обеспечивая режим деления на полином g(X). Они строятся на основе сумма- торов по модулю два и сгруппированы так, что четыре двухвходовых сумматора можно построить на основе одной микросхемы типа К155ИП2, а осталь- ные схемы - на микросхемах типа К155ЛП5.

В предлагаемом устройстве на два умножителя и на один блок сумматоров по модулю два меньше и на один блок инверторов больше, чем в известном.

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

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

Устройство для кодирования, содержащее первый буферный регистр, выходы которого подключены к первым

0

5 о

Q

5

5

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

J 1 1

A

5

6 7 8

Изобретение относится к вычис- - лительной технике. Его использование в системах передачи информации позволяет повысить надежность устройства. Устройство для кодирования содержит умножители 1,2 на постоянную величину, блок 4 элементов И, буфер ные регистры 5-8, блоки 9-11 сумматоров по модулю два и блок 12 ключей. Благодаря введению блока 3 эле ментов НЕ и соответствующим соединением, в устройстве осуществляется деление на полином g(x), имеющий более простой вид, чем в известном устройстве, что и обеспечивает -его упрощение. 3 ил. ( (Л

иг.2