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

 

(») 526883

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик.\

I (61) Дополнительное к авт. свид-ву (22) Заявлено 23.10.74 (21) 2070460/24 с присоединением заявки № (23) Приоритет

Опубликовано 30.08.76. Бюллетень № 32

Дата опубликования описания 22.11.76 (51) М. Кл.з G 06F 5/00

Государственный комитет

Совета Министров СССР по делам изобретений и открытий (53) УДК 681.325 (088.8) (72) Авторы изобретения

А, А. Давыдов и Г. М. Тененгольц

Ордена Ленина институт проблем управления (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ КОДА

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

Известны кодирующие устройства кодов, исправляющих одиночный пакет ошибок, содержащие входной регистр, блок суммирования по модулю два и блок задержки (1). Недостатком их является низкое быстродействие.

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

Однако такое устройство имеет невысокое быстродействие при передаче информации по каналу связи, что объясняется большим количеством избыточных символов, добавляемых известным устройством к информационным символам.

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

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

5 и блоком суммирования по модулю два. К выходу блока группирования символов подключены последовательно соединенные блок подсчета количества единиц> комм ) татор и блок вычисления вычета взвешенной суммы, выход

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

На чертеже показана блок-схема предлага)5 емого устройства, где 1 — выход устройства, 2 — входной регистр, 3 — блок суммирования по модулю два, 4 — блок задержки, 5 — блок группирования символов, 6 — блок подсчета количества единиц, 7 — коммутатор, 8 — блок вычи20 сления вычета взвешенной суммы, 9 — блок защиты вычета взвешенной суммы, 10 — 13— входы блока, 14 — выход устройства.

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

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

25 виде двоичной последовательности информационных символов (I) (I) (т) (з) (з) (з).

Хд, Х2,..., Х;р, Хт, ХЗ т - Я т (Ч (а) (а). хт, х2,..., х

526883 двойки, 35

50

3 (где х — =0,1 для всех s, j), поступает во (i)

S =-" входной регистр 2 и одновременно проходит на вход 10 блока 4. Количество информационных символов равно k.(4), где k и (4> — произвольные натуральные числа. Из входного регистра информационные символы поступают в блок 5. В блоке 5 из информационных символов составляется /г групп: х(), х(> х<Е ). Каждая группа состоит из информационных символов, причем е -я группа x0) содержит информационные символы х<1» х <Е), . ... хф (где е = 1, 2,, k)

Группы информационных символов с выхода блока 5 поступают на входы блоков 3 и б. В блоке 3 вычисляется первое множество контрольных символов. Это множество состоит из b контрольных групп, причем величина

Ь имеет следующий смысл: в информ" öèè, закодированной с помощью предлагаемого устройства, можно исправить любой. одиночный пакет асимметричных ошибок длины (b — 1)(о+1 или менее. Кроме того, исправляются некоторые пакеты длины от (b — 1) е>+2 до b (4). Обозначим группы контрольных символов через х<ь+ ) х("+ >, х< + ) Каждая такая группа состоит из (4) двоичных контрольных символов, причем е-я группа x), х <"+>), ..., xÄ=0,1 для всех

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

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

j ь

k х(ь+ь-J) W x

8 е — o

k J — ЕЬ-.. ( (j=0, 1,..., b — 1; s=l, 2,...,w), где Z — знак суммирования по модулую два.

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

В блоке 6 подсчитывается количество единиц R(I) в каждой группе информационных символов х<». Через коммутатор 7 коды чисел

R(I) поступает в блок 8, где вычисляется вычет В взвешенной суммы в соответствии с формулой

Й

>ь(ь I

B = res, е е((ь — е — (— > ), res А (mod P), Е=1 J=O где res А (modP) означает наименьший неотрицательный вычет А по модулю P. Модуль Р

)о

)5

2О

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

P 2" 2ый+ l.

Вычет взвешенной суммы вычисляется олоком

8 в двоичной форме, т. е. В=р„, ь ..., P>go, где р<=0,1 для i=0,1,..., m — 1. Двоичная запись вычета В является вторым множеством контрольных символов и поступает с выхода блока

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

В блоке 9 в случае, когда вид искажений (О 1 или 1 О) заранее неизвестен, вычисляется количество No(B) нулей среди символов р,, ь ..., P>, Po, Двоичное представление числа Лео(В) имеет вид No(B) =n, I, ...,n>no, где z=)logjam(, n=0,1 для всех i. Это представление, полученное в блоке 9, является третьим множеством контрольных символов и поступает на вход 13 блока 4. Если вид искажений заранее известен (есть и такие каналы), то третье множество контрольных символов, получаемое в блоке 9, состоит из одного бита, а именно из инверсии символа

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

В блоке 4 входная последовательность информационных символов и три множества контрольных символов претерпевают определенные задержки и формируются в кодовое слово х(х ) + (+) х1 ...х ...х1 ...х хе ...х

<ь4 ь) one — Е ° ° ° nor готовое для передачи в канал связи.

Пример. Пусть oI)=3, А=б, b=3. Это означает, что в информации, закодированной с помощью предлагаемого устройства, можно исправить любой одиночный пакет асимметричных ошибок длины (3 — 1)3+1=7. Кроме того, исправляются некоторые пакеты длины

8и9.

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

= 0 1 0 1 1 1 000 1 1 0 001 001 .

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

=000, х(4)=110, х(6)=001, х<6)=001. В блоке

3 вычисляется первое множество контрольных символов, состоящее из трех контрольных групп х<">=х(>+x<4> 100. х<6)=х< >+x<6>=

=110, х< >=х< )+х< )=001. (Здесь + означает поразрядную сумму по модулю два).

В блоке 6 подсчитывается количество единиц R<)) в каждой группе информационных символов x(I) Результаты подсчета Р< )=1, R<Я) = 3 R(з) =0 R<4) =2 R(ü6) )1, R"6) = 1

526883

В блоке 8 вычисляется вы ет Б взвешенной суммы

) З(З вЂ” I

+ 1 (в — j — (г — 1) 3)

i =I j=0

2 2

= гез g Я(в-j ) + 2 1((0 1 з) (mod P) =

1=0 j=0

= res (1 (в) + 1 (з) + 4(4)) + 2 р;)(3)+у (2)+ р(ц) р

X (mod P) = res12(modP).

Поскольку 2<2@+1=2 . 3 6+1=37, то т=

= 6 и P =2 = 64. Следовательно, В = 12.

Двоичная запись В имеет вид В =

= рзр4рзрффо — — 001100. Таким образом, второе множество контрольных символов имеет вид 001100. Так как z=)log2(=3 и Ж0(В) =

=4, то третье множество контрольных символов, вычисляемое в блоке 9, можно записать так: 100. В канал связи передается последовательность

010 111 000 110 901 () х(2) (3) (4) () информация оо1 ио пв оо1 оо1 — oo 1оо (в) ог(ч);с(в) х() В Н,(В) » контрольные символы

Основным преимуществом предлагаемого устройства является повышение быстродействия при передаче информации по каналу связи, что объясняется сокращением количества избыточных символов, добавляемым предлагаемым устройством к информационным символам.

Ведем обозначения г,р,, ruon. — количество избыточных двоичных символов, добавляемых к информационным символам соответственно предлагаемым устройством и известным устройством (патент США № 3.648.238); 1 — длина исправляемого двоичного пакета несимметрпчных ошибок, v — количество информаIl, oHliblê символов, тогда г„„.=о+-41 — 2.Для предлагаемого устройства l=(b — 1)n+I,где

Ь w — целые числа r„o=bw+)log2(2v+1) (+

5 +)log2)log2(2m+I) ((. Поскольку Ьв(1 и

) log2(2v+1) (существенно меньше, чем

v, то г„р существенно меньше г„„. Так, при

v=100, Iv=10, 1=21, получим r„,„=100+

+420 — 2= 178. 1= (b — 1) 10+1, следовательЬ=З. „р — 3 . 10+)log2(2 100+1) (+

+)1о@)1о@2201 ((= 30-,-8+ 3 =41, т. е. для рассматриваемого примера гпр более чем в четыре раза г„„. За счет уменьшения избыточности сокращается скорость передачи информации по каналу связи.

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

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

30 подсчета количества единиц и блок группирования символов, включенный между входным регистром и блоком суммирования по модулю два, к выходу блока группирования подключены последовательно соединенные блок под35 счета количества единиц, коммутатор и блок вычисления вычета взвешенной суммы, выход которого подключен непосредственно к третьему входу блока задержки и через блок защиты вычета взвешенной суммы подключен

40 к четвертому входу блока задержки.

Источники информации, принятые во внимание при экспертизе:

1. Питерсону. Коды, исправляющие ошибки, М. «Мир», 1964, с. 168, рис. 8.1, с. 169 рис. 8.2.

45 2. Патент США ¹ 3648238, кл, 340 — 1461, 1972, Редактор T. Рыбалова

Составитель А. Шкатулла

Техред 3. Тараненко

Корректор Л. Котова

Заказ 2196/2 Изд. Жя 1653 Тираж 864 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

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

Типография, пр, Сапунова, 2