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

(51) М, Кл,2 6 06 присоединением за Государственныи комитет овета Министров СССР по делам изобретений и открытий(23) ПриоритетОпубликовано 30.08.76. Бюллетень32 УДК 681.325 (088. исанпя 2 а опубликования 2) Авторы изобретения А. Давыдов и Г. М. Тененгольц т 71) Заявитель дена Ленина институт пробл равления 4) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ КО(а) (а) (1Х 2 зХЯ 30 Изобретение относится к области вычислигельной техники и может быть использовано в системах передачи и хранения информации в качестве кодирующего устройства кода, исправляющего одиночный пакет асимметричных ошибок.Известны кодирующие устройства кодов, исправляющих одиночный пакет ошибок, содержащие входной регистр, блок суммирования по модулю два и блок задержки 11). Недостатком их является низкое быстродействие.Наиболее близким по технической сущности к изобретению является устройство для формирования кода, содержащее входной регистр, блок суммирования по модулю два и блок задержки, первый вход которого соединен с входом входного регистра, второй вход - с выходом блока суммирования по модулю два, а выход блока задержки соединен с выходом устройства 2).Однако такое устройство имеет невысокое быстродействие при передаче информации по каналу связи, что объясняется большим количеством избыточных символов, добавляемых известным устройством к информационным символам.Цель изобретения - повышение быстродействия устройства.Это достигается тем, что предлагаемое устройство содержит коммутатор, блок вычисления вычета взвешенной суммы, блок защиты вычета взвешенной суммы, блок подсчета количества единиц и блок группирования символов, включенный между входным регистром 5 и блоком суммирования по модулю два. К выходу блока группирования символов подключены последовательно соединенные блок подсчета количества единиц, коммутатор и блок вычисления вычета взвешенной суммы, выход 10 которого подключен непосредственно к третьему входу блока задержки и через блок защиты вычета взвешенной суммы подключен к четвертому входу блока задержки.На чертеже показана блок-схема предлага емого устройства, где 1 - выход устройства,2 - входной регистр, 3 - блок суммирования по модулю два, 4 - блок задержки, 5 - блок груп- пирования символов, 6 - блок подсчета количества единиц, 7 - коммутатор, 8 - блок вычи сления вычета взвешенной суммы, 9 - блокзащиты вычета взвешенной суммы, 10 - 13 - входы блока, 14 - выход устройства.Устройство работает следующим образом.Сообщение, которое нужно закодировать в 25 виде двоичной последовательности информационных символов(,Е)8:входной регистр 2 и одновременно проходитна вход 10 блока 4. Количество информационных символов равно ее в, где Й и (ее - произвольные натуральные числа. Из входного регистра информационные символы поступаютв блок 5. В блоке 5 из информационных символов составляется Й групп; х, х,х(Е). Каждая группа состоит из информационных символов, причем е-я группа х( содержит информационные символы х(Е) х(Е)хее) (где е= 1, 2 й).Группы информационных символов с выхода блока 5 поступают на входы блоков 3 иб. В блоке 3 вычисляется первое множествоконтрольных символов. Это множество состоит из Ь контрольных групп, причем величинаЬ имеет следующий смысл: в информации, закодированной с помощью предлагаемого устройства, можно исправить любой одиночный пакет асимметричных ошибок длины(Ь - 1)(о+1 или менее. Кроме того, исправляются некоторые пакеты длины от (Ь - 1)к)+2до Ь (е), Обозначим группы контрольных символов через х(ь+) х("+4, х(+ь) Каждая такая группа состоит из в двоичных контрольных символов, причем е-я группа х(ь+л содержит контрольные символы х,(", х,(+В,х,(Я, где )=1, 2 Ь; хР+1)=0,1 для всехЕ, 5,Контрольные группы вычисляются блоком3 в соответствии с соотношением 1 ь 1 ь(У = О, 1, , Ь - 1; 6 = 1, 2, , ы),где Х - знак суммирования по модулую два. ) А- суть ближайшее к А целое число, не меньшее А, Таким образом, блок 3 вычисляет контрольные группы, осуществляя поразрядное суммирование по модулю два информационных групп, При этом номера информационных групп, участвующих в образовании одной и той же контрольной группы, отличаются друг от друга на величину Ь. Первое множество контрольных символов поступает из блока 3 на вход 11 блока 4.В блоке 6 подсчитывается количество единиц Р( в каждой группе информационных символов х(. Через коммутатор 7 коды чисел Р( поступает в блок 8, где вычисляется вычет В взвешенной суммы в соответствии с формулойь) ь 1 ь-еВ = гез ь е Р еь - е в ( в , гез А (п)ос 1 Р),Е:1 Е:О где гез А (п)ос 1 Р) означает наименьший неотрицательный вычет А по модулю Р. Модуль Р 5 )О )5 20 25 30 задается как наименьшая степеньудовлетворяющая неравенствуР =-2" )2 ый+1. Вычет взвешенной суммы вычисляется олоком 8 в двоичной форме, т. е. В=фв 1 - ь , ргро, где р(=0,1 для е=0,1 т - 1. Двоичная запись вычета В является вторым множеством контрольных символов и поступает с выхода блока 8 на вход блока 9 и на вход 12 блока 4.В блоке 9 в случае, когда вид искажений (О в 1 или 1 в О) заранее неизвестен, вычисляется количество ЛЕО(В) нулей среди символов Рп ь , Р(, РО, Двоичное пРедставление числа Лео(В) имеет вид Лео(В) =п ь,п)по, где г=1 одт, п=0,1 для всех е. Это представление, полученное в блоке 9, является третьим множеством контрольных символов и поступает на вход 13 блока 4. Если вид искажений заранее известен (есть и такие каналы), то третье множество контрольных символов, получаемое в блоке 9, состоит из одного бита, а именно из инверсии символа При декодировании третье множество контрольных символов используется для обнаружения ошибок в вычете взвешенной суммы.В блоке 4 входная последовательность информационных символов и три множества контрольных символов претерпевают определенные задержки и формируются в кодовое слово х( х )+(+)х+(ь+ь) (ь ь)хехдр е,п, 1 п готовое для передачи в канал связи.Пример. Пусть се)=3, А=б, Ь=З. Это означает, что в информации, закодированной с помощью предлагаемого устройства, можно исправить любой одиночный пакет асимметричных ошибок длины (3 - 1)3+1=7. Кроме того, исправляются некоторые пакеты длины 8 и 9,Сообщение, которое нужно закодировать, имеет видВ блоке 5 из информационных символов составляется 6 групп: х=010, хР)=111, х(Р)= =000, х(4)=110, х(6)=001, х=001. В блоке 3 вычисляется первое множество контрольных символов, состоящее из трех контрольных групп х(") = х+х(4) = 100. х = х-1-х = =10, х=х(з)+х(6)=001. (Здесь + означает поразрядную сумму по модулю два).В блоке 6 подсчитывается количество единиц У в каждой группе информационных символов х(. Результаты подсчета У)=1, Уа) 3 Уз) 0 У 4) 2 У 6) 1 У 6); (п)о(1 Р) = гез 12(п)одР).Поскольку 2 ы 4+1=2 3 6+1=37, то т= = 6 и Р= 2= 64. Следовательно, В = 12. Двоичная запись В имеет вид В = =):зрдзР 2 р 1 рю=001100. Таким образом, второе множество контрольных символов имеет вид 001100. Так как г= 1 од 21,=3 и о(В) = =4, то третье множество контрольных символов, вычисляемое в блоке 9, можно записать так: 100. В канал связи передается последовательность010 111 000 110 901х(1) х(2) х(З) х(4) х(6)информация ОО 1 ОО 11 О ОО 1 ОО 11 -ОО 1 ОО х(6) х х(в) х В Жо(В)контрольные символыОсновным преимуществом предлагаемого устройства является повышение быстродействия при передаче информации по каналу связи, что объясняется сокращением количества избыточных символов, добавляемым предлагаемым устройством к информационным символам.Ведем обозначения гпр, гооо. - количествоизбыточных двоичных символов, добавляемых к информационным символам соответственно предлагаемым устройством и известным устройством (патент США3.648,238); 1 - длина исправляемого двоичного пакета несимметрпчных ошибок, о - количество информац,;онных символов, тогда гоо.=о+41 - 2.Для предлагаемого устройства 1= (Ь - 1) и+1, где Ь,в - целые числа г,р=Ь(о+1 од 2(2 о+1) + 5 +1 о)о 21 од 2(2 ю+1) . Поскольку Ьв(1 и1 од 2 (2 о+1)существенно меньше, чем О, тО Г,р СУЩЕСТВЕННО МЕНЬШЕ Г 11 ов. ТаК, ПРИ о=100, со=10, 1=21, получим гцоо -- 100+ +420 в178. 1= (Ь - 1)10+1, следовательно Ь=3. гпр 3 10+1 ОД 2(2 100+1) + + 1 од 21 од 2201= 30+ 8+ 3 = 41, т. е. для рассматриваемого примера грр более чем в четыре раза г. За счет уменьшения избыточности сокращается скорость передачи ин- (5 формации по каналу связи. Формула изобретенияУстройство для формирования кода, содер 20 жащее входной регистр, блок суммированияпо модулю два и блок задержки, первый входкоторого соединен с входом входного регистра, а второй вход - с выходом блока суммирования по модулю два, а выход блока задер 25 жки соединен с выходом устройства, о т л ич а ю щ е е с я тем, что, с целью повышениябыстродействия, оно содержит коммутатор,блок вычисления вычета взвешенной суммы,блок защиты вычета взвешенной суммы, блок30 подсчета количества единиц и блок группирования символов, включенный между входнымрегистром и блоком суммирования по модулюдва, к выходу блока группирования подключены последовательно соединенные блок под 35 счета количества единиц, коммутатор и блоквычисления вычета взвешенной суммы, выходкоторого подключен непосредственно к третьему входу блока задержки и через блок защиты вычета взвешенной суммы подключен40 к четвертому входу блока задержки.Источники информации, принятые во вни.мание при экспертизе:1. Питерсону. Коды, исправляющие ошибки,М. Мир, 1964, с. 168, рис. 8.1, с. 169 рис. 8.2.45 2. Патент США Ко 3648238, кл, 340 - 1461,1972,Заказ 2196/2 Изд, Жо 1653 Тираж 864 Подписное ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий 113035, Москва, )К, Раушская наб., д. 4/5 Типография, пр, Сапунова, 2