Устройство кодирования и декодирования с обнаружением ошибок в сообщениях переменнойдлины

 

32846I

О П И СА Н И Е

ИЗОБРЕТЕНИЯ

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

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

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

Ресаубяик

Зависимое от авт. свидетельства №вЂ”

Заявлено 19 т/.1970 (№ 1445057/1824) с присоединением заявки №вЂ”

Приоритет

Опубликовано 02.11.1972. Бюллетень ¹ 6

Дата опубликования описания 22.1II.1972

М. Кл. 6 06f 11/00

Комитет оо деяам изобретений и сткрмтий ори Совете Министров

СССР

УДК 681.326.75(088.8) Г " "= .г, .1В. Л, Бахрах, И. М. Бояринов и Г. М. Тененгольц, t i yË - о (Институт проблем управления (автоматики и телемехдникй,)-, Авторы изобретения

Заявител ь

УСТРОЙСТВО КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ

С ОБНАРУ)КЕНИЕМ ОШИБОК В СООБЩЕНИЯХ ПЕРЕМЕННОЙ

ДЛИНЫ

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

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

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

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

Схема устройства изображена на чертеже.

Устройство содержит блок 1 управления, счетчик 2, сумматоры 8, анализатор 4 ошибок, клапан 5, регистр сдвига с разрядами б, триггерные ключи 7.

Сумматоры 8 и ключи 7 установлены лишь в тех разрядах регистра, которые соответствуют ненулевым коэффициентам полиномов

g(x) и g;(x) (1(m). Остальные же разряды регистра сдвига соединены друг с другом не10 посредственно.

На основании статистических данных о длинах сообщений делят интервал длин сообщений на диапазоны. Каждому диапазону длин ставят в соответствие циклический код с тре15 буемой корректирующей способностью. Так, если число диапазонов длин равно т, то первому диапазону ставят в соответствие код с порождающим многочленом д,(х), второму— дз(х),, (m — 1) - му — g„, (х), m-му

20 g(x) = g„,(õ) Н.О.К(а1(х), g (õ),..., gm — 1 (- ) ) °

Процедура кодирования состоит в введении избыточности в сообщение согласно диапазону длин, к которому оно относится. Для это25 го в начальный момент кодирования сообщения, когда длина не установлена, его делят на многочлен g(x). Если сообщение принадлежит диапазону максимальной длины, то полученный остаток является проверочной частью ко30 дового слова. В противном случае делят иолу328461

65 зченный остаток на многочлен g;(x) (i ())L), который соответствует диапазону длин для данного сообщения. Полученный остаток является проверочной частью кодового слова.

Процедура декодирования заключается в том, что полученное сообщение делят на многочлен g(x). Если остаток равен пулю, то ошибок нет. Если же остаток не равен нулю, а сообщение принадлежит m-му диапазону, то в сообщении содержится ошибка.

Когда остаток отличен от нуля, а сообщение принадлежит 1-му диапазону (i (m), проводят деление полученного первоначального остатка на g,(õ). Если образованный в результате этого деления остаток равен нул1о, то ошибок нет, в противном случае обнаружена ошибка.

Счетчик 2 предназначен для определения длины поступившего сообщения и установления принадлежности его соответствующему диапазону длин. Блок 1 управления содержит дешифраторы кодовых комбинаций «начало» и «конец» на регистрах с диодными матрицами и ряд элементов, выполняющих функции логического управления работой устройства.

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

В исходном состоянии выходы блока 1 управления на сумматор 8 первого разряда б регистра сдвига и на счетчик 2 закрыты. На входы блока управления, подсоединенные к анализатору 4 ошибок и клапану 5, сигнал не поступает. Счетчик 2 установлен в «нуль», и поэтому сигналы по любому из его выходов отсутствуют. Ключи 7 находятся в положении прямой коммутации разрядов б регистра сдвига между собой. Регистр сдвига установлен в

«нуль».

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

«начало». Как только дешифратор блока управления определит, что «начало» сообщения поступило, информационная часть его поступает на вход указанного сумматора и одновременно па вход счетчика 2. В этот моме1!т выход счетчика, соответствующий т-му диапазону длин, обеспечивает подключение части сумматоров 3 через ключи 7 к разрядам б регистра сдвига, соответствующим ненулевым коэффициентам полинома g(x). Остальные сумматоры зашуптировапы связями разрядов между собой через ключи.

В разрядах регистра сдвига формируется остаток от деления. В момент, когда дешифратор блока управления определит кодовуюкомбинацию «конец» сообщения (через число тактов, соответствующих числу разрядов в этой комбинации), закрываются выходы блока управления на первый сумматор 8 и на счетчик.

В результате этого вырабатывается с 1П1ал, 5

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

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

В том случае, когда сообщение принадлежит

i-му (i (т) диапазону длин, сигнал с соответствующего выхода счетчика осуществляет переключение ключей, подключая сумматоры к ячейкам регистра сдвига в соответствии с ненулевыми коэффициентами полинома д;(х).

После этого переключения остаток, сформированный в ячейках регистра сдвига, делится на полином g,(х). По завершению этой процедуры устройство работает так же, как в случае, когда сообщение принадлежало m-му диапазону, с той лишь особенностью, что длина проверочной части, считываемой через блок управления на выход 8, меньше длины проверочной части для т-го диапазона. Анализатор ошибок при кодировании сообщений, участия в работе устройства не принимает.

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

«конец». Затем по сигналу с блока управления осуществляется параллельный опрос разрядов регистра сдвига анализатором ошибок. Если остаток от деления равен нулю, то ошибок нет, независимо от того, какому из диапазонов длин принадлежит принятое сообщение, Если же остаток от деления отличен от нуля и сообщение не принадлежит т-му диапазону длин, то по сигналу счетчика, свидетельствующему о принадлежности принятого сообщения

i-му (i (т) диапазону длин, происходит переключение соответствующих ключей и подключение соответствующих сумматоров между разрядами регистра сдвига, После этого, за определенное число тактов сдвига, ранее образованный остаток делится на g,(õ). Вновь по сигналу с блока управления проводится о»рос регистра. Если остаток от деления равен нулю, то сообщение принято без ошибок, в противном случае оно ошибочно.

При выполнении описанных операций контрольная часть для сообщений L-го диапазона образуется в разрядах регистра, соответствующих L-му диапазону, и занимает число разрядов, равное степени i-го полинома, при этом разряды регистра отсчитываются от первого слева разряда регистра сдвига.

Контрольная часть считывается в канал связи через сумматор первого разряда вслед за информационной частью. B регистре сдвиI.a после считывания проверочной части содержатся нули.

Степень образующего полинома при перехо де с f)l Î ди)1паз01111 L è диан!!зон (L ()и) из328461

Составитель В. Игнатущенко

Текред Т. Ускова

Редактор И. Грузова

Корректор Л. Бадылама

Заказ 675, 18 Изд. № 172 Тираж 448 Подписное

111-1ИИПИ Когяитета по дслагя изобретений и открытий при Совете Министров СССР

Москва, 7К-35, Раугнская нао., д. 4 5

Типография, ир. Сапунова, 2 меняется на величину, равную разности степеней многочленов g(x) и g;(x).

Предмет изобретения

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