Устройство для формирования кода Советский патент 1976 года по МПК H03M13/03 

(где -- 0,1 для всех s, /), поступает во

S. входной регистр 2 и одновременно нроходит на вход 10 блока 4. Количество информационных символов равно k-w, где k HW - произвольные натуральные числа. Из входного регистра информационные символы поступают в блок 5. В блоке 5 из информационных символов составляется k групп: , х( ..., х ). Каждая группа состоит из информационных символов, причем /-я группа л;® содержит информационные символы x{J xf-) . . ... х( {где/ 1, 2,...,k).

Группы информационных символов с выхода блока 5 поступают на входы блоков 3 и 6. В блоке 3 вычисляется первое множество контрольных символов. Это множество состоит из b контрольных групп, причем величина b имеет следующий смысл: в информации, закодированной с помощью предлагаемого устройства, можно исправить любой, одиночный пакет асимметричных ошибок длины (Ь-1)ш + 1 или менее. Кроме того, исправляются некоторые пакеты длины от (Ь-)w-{-2 до b W. Обозначим группы контрольных символов через xC+i, х(+2, ..., л:(+). Каждая такая группа состоит из ш двоичных контрольных символов, причем /-я группа . содержит контрольные символы A:I( + ), . . .,

где , 2, .,..6; , для всех

/, S.

Контрольные группы вычисляются блоком

3 в соответствии с соотношением

4н

l)

у x(-j-ib)

-

6-/-/ 3-1

(у 0, 1,..., 6-1; s l, 2,...,w),

где 2 - знак суммирования по модулую два. А - суть ближайшее к А целое число, не меньшее А. Таким образом, блок 3 вычисляет контрольные группы, осуществляя поразрядное суммирование по модулю два информационных групп. При этом номера информационных групп, участвующих в образовании одной и той же контрольной группы, отличаются друг от друга на величину Ь. Первое множество контрольных символов поступает из блока 3 на вход 11 блока 4.

В блоке 6 подсчитывается количество единиц в каждой группе информационных символов А;0). Через коммутатор 7 коды чисел () поступает в блок 8, где вычисляется вычет В взвещенной суммы в соответствии с формулой

Аг

I Ь-1

B res i 2/( --- -), res А (mod Я),

где res А (mod/) означает наименьщий неотрицательный вычет А по модулю Р. Модуль Р

задается как наименьшая степень двойки, удовлетворяющая неравенству

Я 32 2wk-i-l.

Вычет взвешенной суммы вычисляется олоком 8 в двоичной форме, т. е. -, PiPo, где Рг 0,1 для ,1, . .., т-1. Двоичная запись вычета В является вторым множеством контрольных символов и поступает с выхода блока

8 на вход блока 9 и на вход 12 блока 4.

В блоке 9 в случае, когда вид искажений (О 1 или 1 0) заранее неизвестен, вычисляется количество Мо(В) нулей среди символов Pm-i, ..., PI, РО. Двоичное представление

числа NO(B) имеет вид A/o(B)z-b ...,П1По, где , л 0,1 для всех i. Это представление, полученное в блоке 9, является третьим множеством контрольных символов и поступает на вход 13 блока 4. Если вид искажений заранее известен (есть и такие каналы), то третье множество контрольных символов, получаемое в блоке 9, состоит из одного бита, а именно из инверсии символа рт-ь При декодировании третье множество контрольных символов иснользуется для обнаружения ошибок в вычете взвешенной суммы. В блоке 4 входная последовательность информационных символов и три множества контрольных символов претерпевают определенные задержки и формируются в кодовое слово

ri

.(ft) v.( + I)

.()

V.V

4f} ( . . Л1 p . -A/Jy л J

.

) (k+l)

. Hi-l . Лда

. . . р(,«г-1 ... «0.

готовое для передачи в канал связи.

Пример. Пусть w 3, и -6, Ь 3. Это означает, что в информации, закодированной с помощью предлагаемого устройства, можно исправить любой одиночный пакет асимметричных ошибок длины (). Кроме того, исправляются некоторые пакеты длины 8 и 9.

Сообщение, которое нужно закодировать, имеет вид

х Af х ;сР 4 4 х{ 4 -Р X X. .r.xf r 4;cf ;c « ;c) 010 111 000 110 001 001.

в блоке 5 из информационных символов составляется 6 групп: .х()010, А;()111,

000, л:()110, х(, х(б)001. В блоке

3 вычисляется первое множество контрольных

символов, состоящее из трех контрольных

групп л;(7)л:(1)-|-д;()100. л:(«) л;(2)Ч-jc(5)

110, л:(3).л;(3)+х(б)оо1.(Здесь + означает

поразрядную сумму по модулю два).

В блоке G подсчитывается количество единиц /() в каждой группе информационных символов Результаты подсчета ./( , /(2) 3, /(3)0, /()2, R()l, В блоке 8 вычисляется вычет В взвешенной 5: res 2 () - res 2 - + 22 ;(б-/-з) (mod Я) - res ;() + у9(5) ;(4)| 2 /(3)-|-(2)/(1) X X (mod Я) res 12 (mod Р). Поскольку 3 , то /п 6 и . Следовательно, . Двоичная запись В имеет вид В Р5р4рз|32р1|Зо 001100. Таким образом, второе множество контрольных символов имеет вид 001100. Так как 3 log2m 3 и No(B) 4, то третье множество контрольных символов, вычисляемое в блоке 9, можно записать так: 100. В канал связи передается последовательность010 111 000 ПО 901 (1) JC(2) Л;(3) л;(4) ;с(5) информация 001 100 ПО 001 0011-00 100 jc(6) г( jc(8) л:(9) В N(B) контрольные символы Основным преимуществом предлагаемого устройства является повышение быстродей ствия при передаче информации по каналу связи, что объясняется сокращением количе ства избыточных символов, добавляемым пред лагаемым устройством к информацио 1 1ым символам. Ведем обозначения Гпр., Гиэп. - количество избыточных двоичных символов, добавляемых к информационным символам соответственно предлагаемым устройством и известным уст ройством (патент США № 3.648.238); / - дли на исправляемого двоичного пакета несим етричных ошибок, V - количество информа :ониых символов, тогда Гиэв. . Для редлагаемого устройства ),где ,w - целые числа rnp bw-{- log2(2v+l) + (2ay+l) Поскольку и og2(2u+l) существенно меньше, чем V, то Лпр существенно меньше Гиэв. Так, при у 100, , , получим 4-420-2 178. /(6-1)10+1, следовательно Ь 3. - ,(2- 100+1) -f + log2 log2201 30 + 8-f3 41, т. е. для рассматриваемого примера Гпр более чем в четыре раза Гиэв- За счет уменьшения избыточности сокрашается скорость передачи информации по каналу связи. Формула изобретения Устройство для формирования кода, содержащее входной регистр, блок суммирования по модулю два и блок задержки, первый вход которого соединен с входом входного регистра, а второй вход - с выходом блока суммирования по модулю два, а выход блока задержки соединен с выходом устройства, отличающееся тем, что, с целью повышения быстродействия, оно содержит коммутатор, блок вычисления вычета взвешенной суммы, блок защиты вычета взвешенной суммы, блок подсчета количества единиц и блок группирования символов, включенный между входным регистром и блоком суммирования по модулю два, к выходу блока группирования подключены последовательно соединенные блок подсчета количества единиц, коммутатор и блок вычисления вычета взвешенной суммы, выход которого подключен непосредственно к третьему входу блока задержки и через блок защиты вычета взвешенной суммы подключен к четвертому входу блока задержки. Источники информации, принятые во внимание при экспертизе: 1. Питерсону. Коды, исправляющие ошибки, М. «Мир, 1964, с. 168, рис. 8.1, с. 169 рис. 8.2. 2. Патент США Х 3648238, кл. 340-1461, 1972.