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

 

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

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

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

РЕСПУБЛИК

y1) 4 Н 03 И 13/02

Ir сг..-.-,.

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ;., „..: Ц

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4029487/24-24 (22) 26.02.86 (46) 23.04.88. Бюл. ¹ 15 (71) Пензенский политехнический институт (72) Б.А.Савельев (53) 681.325(088.8) (56) Заявка Японии № 58-45738, кл. G 06 F 11/10, 1983.

Питерсон У., Уэлдон К. Коды, исправляющие ошибки. — M.: Мир, 1976, с. 253-254, рис. 8.2, 8.3.

„SU,, 1390801 А1 (54) УСТРОЙСТВО ДЛЯ КОДИРОВАНИЯ (57) Изобретение относится к вычислительной технике. его использование в системах передачи информации позволяет повысить надежность устройства. Устройство для кодирования содержит умножители 1,2 на постоянную величину, блок 4 элементов И, буфер» ные регистры 5-8, блоки 9-11 сумматоров по модулю два и блок 12 ключей. Благодаря введению блока 3 эле» ментов НЕ и соответствующим соединением, в устройстве осуществляется деление на полином g(x), имеющий более простой вид, чем в известном устройстве, что и обеспечивает .его упрощение. 3 ил.

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

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

На фиг. 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 по модулю два.

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

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

f(Х) — полинам, К коэффициентов котол-< рого при слагаемых, содержащих Х

Х, ..., Х", выбраны информационными символами, а коэффициенты при слагаемых Х со степенями, меньшими п-К, равны О. Такому многочлену соответствует вектор, первые К компонент которого — информационные символы, а последние п-К компонент равны О.

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

f(х) = g(x) ° g(x) + r(x), тде g(x} — порождающий многочлен кода, в,(х) — полипом информационных символов

r(x) — остаток от деления f(x) на g(x).

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

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

g(x). И признаком кодового блока является деление без остатка полинома

g(x) g(x) íà g(x). Признаком обна10 ружения ошибок в кодовом блоке является возникновение остатка при делении.

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

f (õ) + r(x) = g(x) ° g(x) .

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

20 Поскольку первая часть выражения (?} — кодовый блок, то и левая часть также делится без остатка íà g(x).

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

30 информационных символов К(Х) необхон-к димо умножить на Х, в результате чего получают f(X), младшие п Ê разрядов которого равны 0 и с которыми необходимо сложить г(Х) — остаток от деления K(K) Х = г(Х) íà g(X).

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

+ r(X) можно получить с помощью регистра сдвига с обратными связями, содержащего п-К ячеек памяти (регист40 ров). Регистр сдвига строится на основе порождающего многочлена g(X).

Для кодов Рида-Соломона (PC) над полем Галуа GF(q) с длиной n = q-1 порождающий полином находится из вы45 ражения (х) = (х — сС ) (х — с(, )... (х— — сь ), (3) где " — примитивный корень поля Галуа

GF(q), d — кодовое расстояние.

При сложении по модулю два в поле

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

g(x) = (х + К ) (х + g ) ... (х+ сС "), где m — разрядность символов в поле

Галуа.

1390801

001 00000

10001011

1100100

00010000

Наибольшее распространение получили поля Галуа GF(2 ) (m = 8). что соответствует разрядности байта информации.

Сущностью алгоритма кодирования, реализуемого в предлагаемом устройстве, является выбор для порождающего полинома g(x) таких пар сомножителей (Х + ) (Х + ), сумма ко10 эффициентов в которых при переменной

Х становится равной единице, где

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

GF(2 ) n — длина кода К вЂ” число

t У

15 информационных элементов в коде, примитивный элемент поля Галуа GF(2 ) .

0 — 11111111

1 -10000000

2 — 01000000

3 — 00010111

9 — 001 1 01 00

10 — 01110011

11 — 01110000

12 — 1 1000101

13 — 11011000

14-01110010

15 — 01011110

16 — 00001 000

17 — 00010001

18 — 00011010

19 —.10111110

20 — 10111001

При исправлении однократной ошиб&, ки в поле ГГ(2 ), элементы которого образуются с помо;; ью примитивного полинома F(X) = . : + Х + Х + X +1, порождающий многочлен может иметь один из следующих видов

Р (х) =(х +g)(õ +Г ) = х +

+ (< +d)x+, =х +х +

Р (х) = (х + ) (х + gÁ ) = х + г

+ (<+ 4 )х+ 4 =х +к+eL, Элементы поля GF(2 ) (десятичные числа являются степенью «,);

21 — 10101101

22 — 00111000

23 — 11000011

24 — 11100010

25 — 00101010

26 — 01101100

27 — 0 1 0 0 0 0 0 1

28 — 00111001

29 — 11101101

30 — 00101111

31 — 11100011

32 — 00000100

33 — 1 0 1 0 0 0 0 1

34 — 10001000

35 — 0 1 0 1 0 0 Π1

36 — 00001101

37 — 10011110

38 — 01011111

39-00100110

40 — 1 1 0 1 1 1 0 0

41 — 11010011

1390801

42-11010110

43-01011001

44-00011100

45 — 1 00 00 1 Π0

46-11100001

47 -10011111

48-01110001

49-1110101

50 — 00010101

51 -10111011

52 -001 101 10

53 - 1 1 1 О 1 О О О

54 — 1 0 1 0 0 0 0 0

55 — 10100110

56 — 10011100

57 — 11000100

58 -111 λ Î

59 - 1 О 1 1 1 1 1 1

60-10010111

61 — 01100000

62-11110001

63-10101011

64 -0000001 0

65-10011011

66 -11010000

67 -01 10001 1

68-01000100

69-10110110

70 — 1 Π1 Π1.0 0 0

-1O!10»

72-10000110

73 -011 11010

74 - 0 1 0 0 1 1 1 1

75 -0001 0010

76 — 1 0 1 0 1 1 1 1

77 -10100011

78 -0001 001 1

79 -10000001

S0 - 0 1 1 0 1 1 1 0

81-11011010

82 — 11101001

83 — 1 ΠΠΠ1 1 1 0

84 — 01101011

85-01010101

86 - 1 О 1 О 1 1 О О

87-00010110

88-00001110

89-00101011

90 — Π1 0 Π0 Π1 0

91-10001100

92 — 11110000

93-10000101

94-11001111

95-01010010

96 — 1 0 1 1 1 Π0 Π,,97-10000011

98 - 1 1 1 1 О 1 0 1

99 -00001010

1390801

100 — 1 Π0 Π1 0 1 0

101 — 1 1 001 О 1 О

102 — 1 1 Î 1 1 1 0 1

103 — 1 1 1 1 1 1 Π1

104 — 00011011

105 — 10010000 г

106 — 01110100

107 — 01100100

108 — О 1 О 1 О О О О

109 — ΠΠ1 ΠΠΠ1 1

110 — Π1 Π1 ΠΠ1 1

111 — 1 О О 1 О 1 1 О

112 — 01001110

113 — 00111100

114 — О 1 1 О О О 1 О

115 — О 1 1 О 1 О 1 О

116 — Π1 1 1 1 Π1 1

117 — Π1 1 ΠΠΠΠ1

118 — 1 1 Π1 1 1 1 1

119 — 0 1 1 О О 1 1 О

120 — 11001011

121 — 11110011

122 — О О 1 1 О О О О

123 — 1 1 О 1 О О 1 О

124 — 1 1 1 1 1 0 0 0

125 - 1 О О 1 О 1 О О

126 — 1 1 Π1 Π1 Π1

127 — 1 1 1 Π1 1 Π0

128 — ΠΠΠΠΠΠ0 1

12.9 — Π0 1 0 1 1 1 0

130 — 1 1 0 0 1 1 0 1

131 — 1 1 0 Π1 ΠΠ1

132 — 01101000

133 — 1 1 1 О О О О О

134 — 1 Π1 1 0 ΠΠ1

135 — 10111100

136 — О О 1 0 О О 1 О

137 — Π1 1 1 1 1 0 1

138 — 01011011

139 — 10000111

140 — 0 1 О 1 0 1 О О

141 — 10000010

142 — 1 1 Π1 1 Π1 1

143 — 11000111

144 — Π1 ΠΠΠΠ1 1

145 — 1 О 1 О О О 1 О

146 — ΠΠ1 1 1 1 Π1

147 — 0 1 О О 1 1 О О

148 — 1 01 001 1 1

149 — 10110010

150 — ΠΠΠΠ1 ΠΠ1

151 — 001 11 1 1 1

E52 — 11010111

153 — 01110111

154 — 11010001

155 — Π1 ΠΠ1 i Π1

156 — 1 ΠΠΠ1 ΠΠ1

1390801

157 — 0 1 1 1 1 1 1

158 — 1 1 О О 0 0 О О

159 — 0 1 0 1 Π1 1

160 — 0 Π1 1 l 1 1 1

161 — 1 1 0 0 0 1 0

162 — 0 1 1 0 1 1 0 1

163 — Π1 1 Π1 1 1 1

164 — 1 1 1 1 О 1 О О

165 — 00100100

166 — Π1 ΠΠΠ1 1 1

167 — Π0 ΠΠΠΠ1 1

168 — 1 Π1 1 Π1 Π1

169 — 00011101

170 — 1 О 1 О 1 О 1 О

171 — О О 1 О 1 1 О О

172 — О 1 О О 1 1 О

173 — ΠΠΠ1 1 ΠΠ1

174 — ΠΠ00 1 01 1

175 — 1 О 1 О О 1 О О

176 — О О О 0 О

177 — О О О 1 О 1 О О

178 — 1 ΠΠ1 Π1 Π1

179 — 1 1 1 1 1 Π1 1

180 — О О 1 О О О О

181 — 11001000 !

82 — 01000\10

183 — Π0 1 Π1 1 Π1

184 — 01111000

18 — 1 1 Π1 Π1 Π0

186 — 1 1 О О О 0 1 О

187 — 1 1 О О 1 1 О О

188 — 1 1 1 ΠΠ1 1 1

189 — 1 Π1 Π0 1 Πi

190 — ΠΠ1 Π1 Π0 1

191 — 11011001

192 — 01011100 !

93 — 1 ΠΠ1 ΠΠ1

194 — 1 1 ΠΠΠΠΠ1

195 — Π1 1 1 1 ΠΠ1

196 — 1 1 1 1 1 0 1 О

197 — ΠΠΠΠ1 1 1 1

198 — ΠΠΠΠ0 1 Π1

199 — 10001111

200 — Π1 0 ΠΠ1 Π1

201 — 1 0 0 1 1 0 0 0

202 — 01100101

203 — О 1 1 1 1 1 1 О

204 — 1 1 1 0 1 1 1 О

205 — О О 1 1 О 1 С

206 — 1 1 1 1 1 1 i О

207 — 1 О 1 О 1 1 1 О

208 — i ΠΠΠi 1 0 1

209 — 1 1 Π1 1 1 1 0

210 — 01001000

211 — 000001 1 0

212 — 00111010

213 —.01011000

214 — 00110010!

1390801 что

215 — 01001001

216 -001 01 000

217-11110111

218 — 10010001

219 " О 1 0 1 1 О 1 О

220 — 1 Π1 Π1 ΠΠ1

221 — 1 0 Π1 1 ΠΠ1

222 -01001011

223 — 1 0 1 1 ΠΠ1 1

2?4 — ΠΠ1 ΠΠ1 1 1

225 — 1 1 1 1 ΠΠ1 0

226 — О 0 О 1 1 1 1 О

227 — 0001111

228 — ΠΠ1 1 Π1 Π1

229-11111100

"!230 — 001 01 01

231 — Π1 Π1 1 1 Π1

232 — 1 0 1 1 1 1 Π1

233 — ΠΠΠΠ1 1 Π0

234 — 1 Π1 1 ΠΠΠ0

235 - 1 О О 1 0 0 1 0

Из представленных данных видно, IL+ А= 1 н dL + 06

Ы г 59

Для исправления двухкратных ошно, бок целесообразно взять

g(x) = g,(x)g (х) = (х + х +

+ Кн )(х + х + 6 ) = х +

+(к, +1)х + и х+оС

Устройство для кодирования, построенное по полиному g(x) = x + (й + ф

236 — 1 1 1 0 1 1 1 1

237 — 1 О 1 О 1 О О

238 - 0 0 1 1 0 0 1 1

239 — Π1 1 ΠΠ1 1 1

240 — 1 1 1 ΠΠ1 0 1

241 — Π0 1 1 1 1 0

242 — 1 1 1 i 1 0 0 1

243 — 1 Π1 1 1 Π1 0

244 — О О 0 1 1 О 0 О

245 — ΠΠ1 ΠΠ1 0

246 — 01101001

247 — 1 ΠΠ1 1 0

248 — О 1 1 1 1 1 О О

249 - О 1 1 1 О 1 О

250 — О 1 О О i О 1 О

251-10011 i 01

252 — 1 1 1 О 1 О 1 О

253 — ΠΠ1 1 1 Π1 1

254 — Π1 1 1 Π1 0

255 — 1 1 1 1 1 1 1 1

+ 1)х + Ы х + ы, при исправлен г 5h г э двухкратных ошибок, работает след щим образом. . Ф

Информационные символы, количество которых К = n — 4, подаются с входо

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

1390801

l4 ра., It — К выход регистра умножается на Х

Х, где 4 — число проверочных символов. Б устройстве для код!!рован!!я осуществляется деление К(Х)Х ка

54 поликом g(x) = х + (Ф. + 1) х + х + . Деление заканчивается

54 219 т как только и-4 информационных символов поданы ка входы 13, в результате чего в регистре сдвига, составленном из буферных регистров 5-8, получен остаток r(Х) = г Х + кг Х +

„г

+ г,Х + r,. По"ле этого блоки 4 и

12 по первым информационным входам закрываются, а по вторым открываются управляющим сигналом Т2 на входе

16.Проверочные элементы нз регистров

5-8 выводятся вслед за информационными элементами. Таким образом, закодировано сообщение, имеющее длину и байтов.

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

219 54 элементы поля !!, и Ж, обеспеЧивая режим деления на полином

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

К155ПП5.

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

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

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

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

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

Фиг.2

1 390801

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

Техред N.Äèäûê

Редактор С.Патрушева

1<оррек тор 1 . Решетник 1ираж 928

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

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

Подписное

Заказ 1784/56

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