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

СОЮЗ СОВЕТСКИХ СОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 801 19 03 М 13/02и Р п 19 ОСУДАРСТВЕННЫЙ КОМИТЕТ СССР О ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ 4029487/24-226.02.8623.04.88. БюПензенский питутБ.А.Савельев681.325(088,Заявка ЯпониС 06 Р .11/10,итерсон У., Уавляющие ошибс. 253-254,(54) УСТРОЙСТВО ДЛЯ КОДИРОВАНИЯ (57) Изобретение относится к вычислительной технике. Его использование в системах передачи информации позволяет повысить надежность устройства. Устройство для кодирования содержит умножители 1,2 на постоянную величину, блок 4 элементов И, буфер ные регистры 5-8, блоки 9-11 сумматоров по модулю два и блок 12 ключей. Благодаря введению блока 3 эле ментов НЕ и соответствующим соединением, в устройстве осуществляется деление на полином 8(х), имеющий более простой вид, чем в известном устройстве, что и обеспечивает его упрощение. 3 ил.1390801 Составитель О.Ревинск .ехред М,Дидык 1(орректор 1. Решетн дактор С.Патруш одписно аказ 1784 полиграфическое предприятие, г. Ужгород, ул, Проектна роизводстзенно ВНИИПИ Го по дела3035, Моск Рираж 92 арственног зобретений Ж, Рауш омитета СССРоткрытий ая наб., д, 4/5(2) Изобретение относится к вычислительной технике и может быть использовацо в системах передачи ицформации,Цель изобретения - повышение надежности устройства.На Фиг, 1 изображена блок-схема устройства для кодирования,на Фиг.2 и 3 - примеры функциональных схем Первого и второго умножителей для случая иосьмиразрядных символов.Устройгтво для кодирования со 1 держит первый и второй умцожителии 2, блок 3 элементов НГ, блок 4 элементов И, первьй-четвертый буферные регистры 5-8, первый-третий блок 9-11 сумматоров по модулю два и блок12 ключей. На фиг. 1 обозначены инФормационные входы 13, вход 1 ч синхронизации, первый и второй управляющие входы 15 и 16, выходы 17.Первый и второй умножители 1 и 2 могут быггь выполнены (фиг. 2 и 3) ца сумматорах 18-29 и 30-40 по модулю два.В основе работы устройства для кодирования лежит следующее.В кодовых комбинациях кода Рида- Соломона имеется К информационных и и-К проверочных символов, каждый из которых содержит ш в двоичн символов, где и - длина кодовой комбинации (блока), Символы являются элементами поля Галуа СР (2 ), Пусть (Х) - полинам, К коэффициентов котол- рого при слагаемых, содержащих Х Х , , Х" , выбраны информационными символами, а коэффициенты при слагаемых Х со степенями, меньшими п-К, равны О. Такому многочлену соответствует вектор, первые К компонент которого - информационные символы, а последние п-К компонент равны О. В соответствии с алгоритмом деления Евклида Г(х) = в(х) 8(х) + г(х),где д(х) - порождающий многочленкода;ц(х) - полипом информационныхсимволов;г(х) - остаток от деления Й(х)ца у.(х) .Степень мцогочлеца г(х) меньше чемп-К, а ц(х) - равна п-К. Кодовый блок может быть найденкак результат умножения иолиномастепени не выше К, коэффициентамикоторого являются информационныесимволы, на порождающий многочлен8(х). И признаком кодового блока является деление без остатка полинома8(х) 8(х) на д(х). Признаком обна ружения ошибок в кодовом блоке является возникновение остатка при делении,Выражение (1) можно записать в ви. 15 г(х) + г(х) = 8(х) 8(х),При двоичных сигналах вычитаниеможно заменить сложением.20 Поскольку первая часть выражения(2) - кодовый блок, то и левая частьтакже делится без остатка на 8(х).Следовательно, для кодирования можноиспользовать два способа в соответсвии с левой и правой частью выражения(2). Кодирование с помощью левойчасти удобнее, поскольку информационные символы получают в неизменномвиде. В этом случае К коэффициентов 30 информационных символов К(Х) необхон-кдимо умножить на Х , в результатечего получают Г(Х), младшие и-К разрядов которого равны 0 и с которыминеобходимо сложить г(Х) - остатокот деления К(К) Х = г(Х) на 8(Х).Кодовый блок по выражению г(Х) ++ г(Х) можно получить с помощью регистра сдвига с обратными связями,содержащего п-К ячеек памяти (регист ров), Регистр сдвига строится на основе порождающего многочлена (Х),Для кодов Рида-Соломона (РС) над полем Галуа СР(ц) с длиной и = и порождающий полином находится из вы45 Ражения-к" ), (3) где Ь - примитивный корень поля Галуа СР(Ч)с 1 - кодовое расстояние.При сложении по модулю два в поле Галуа СГ(2 ) выражение (3) можно переписать в виде 8(х) = (х + ОС ) (х + С )(х+ К 5,где ш - разрядность символов в поле Галуа,139080 00100000 11100110 100010111100100 00010000 Наибольшее распространение получили поля Галуа СГ(2 ) (в = 8), что соответствует разрядности байта информации.5 Сущностью алгоритма кодирования, реализуемого в предлагаемом устройстве, является выбор для порождающего полинома 8(х) таких пар сомножителей (Х + К ) (Х +), сумма ко 10 эффициентов в которых при переменной Х становится равной единице, где ш - разрядноСть элементов поляСР(2 ) и - длина кода К - числоУ 915 информационных элементов в коде, примитивный элемент поля Галуа СР(2 ),0 - 11111111 1 - 10000000 2 - 01000000 3 - 00010111 9 - 00110100 10 - 0 1 1 1 0 0 1 1 11 - 01110000 12 - 1 1000101 13 - 11011000 4 -01110010 15 - 01011110 16 - 00001000 17 - 00010001 18 - 0 0 0 1 1 0 1 0 19 - 1 0 1 1 1 1 1 0 20 - 10111001 11 ри исправлении однократной ошиб,й,ки в поле СГ(2 ), элементы которогообразуются с помощью примитивногополинома Г(Х) = .: + Х + Х + Х +1,порождающий многочлен может иметьодин из следующих видова (х) =(х + Ы ) (х +Г) - х ++ (Ы, + 1 )х+ О =х +к+юг, Элементы поля СГ(2 ) (десятичные числа являются степенью К ); 21 - 1 0 1 0 1 1 0 1 22 - 00111000 23 - 11000011 24 - 11100010 25 - 00101010 26 - О1 О 1О О 27 - 0 1 0 0 0 0 0 1 28 - 0 0 1 1 1 0 0 1 29 - 11101101 30 - 00101111 31 - 11100011 32 - 0 0 0 0 0 1 0 0 33 - 1 0 1 0 0 0 0 1 34 - 1 О О О 1 О О О 35 - 0 1 0 1 0 0 О 1 36 - О О О О 1 1 О 1 37 - 1 О О1 1 1 О 38 - 0 1 0 1 1 1 1 1 39 -00100110 40 - 1 1 0 1 1 1 0 0 41 - 1 1 О 1 О О 1 12 1390801 что 215 - 01001001 216 - 00101000 217 -11110111 218 -10010001 219 " 0 1 0 1 1 0 1 0 220 - 1 0 1 0 1 0 0 1 221 - 1 0 0 1 1 0 0 1 222 -01001011 223 - 1 0 1 1 0 0 1 1 224 - 0 0 1 0 0 1 1 1 225 - 1 1 1 1 0 00 226 - 0 0 0 1 1 1 1 0 227 - О О О 1 1 1 1 228 - 0 0 1 1 0 1 0 1 229 - 1 1 1 1 1 1 0 0 "230 0 0 10 1 0 1 231 - 0 1 0 1 1 1 0 1 232 - 1 0 1 11 О 1 233 - 0 0 0 0 1 1 0 0 234 - 1 0 1 1 0 0 0 О 235 - 1 0 0 1 0 0 1 0 Из представленных данных видно,4+ А=и К+ К =1. ЧЧ 2 59 Для исправления двухкратных ошибок целесообразно взять К(х) = К (х)8 (х) = (х + х ++ сС )(х + х + д ) = х + + ( Ы + 1)х + й х + , .Устройство для кодирования, пост" роенное по полиному 8(х) = х + (й + 236 - 1 1 1 0 1 1 1 1 237 - 1 0 10 1 0 0 238 - 0 0 1 1 0 0 1 1 239 - 0 1 1 0 0 1 1 1 240 - 1 1 1 0 0 1 0 1 241 - 0 0 1 1 1 1 1 0 242 - 1 1 1 1 1 0 0 1 243 - 1 0 1 1 1 0 1 0 244 - 0 0 0 1 1 0 0 0 245 - 0 0 1 0 0 1 0246 - О 1 1 О 1 О О 1 247 -1 0 01 1 0 248 - 0 1 1 1 1 1 0 0 249 - 01 1 0 1 0250 - 0 1 0 0 1 0 1 0 251 -10011101 252 - 1 1 1 0 1 0 1 0 253 - 0 0 1 1 1 0 1 1 254 - 0 1 1 1 0 10 255 - 1 1 1 1 1 1 1 1+ 1)х + Ы х + Ы з, при исправлен2 Л гздвухкратных ошибок, работает следщим образом. Информационные символы, количество которых К = и - 4, подаются с входо 4 13 параллельно на блоки 11 и 12. Во время подачи информационных снмволо управляющим сигналом Т (К тактовых импульсов) открыт блок 4 и по первый информационным входам - блок 12. В результате информационные еимволы подаются на выходы 17 устройства и в шину обратной связи на входыумножителей 1 и 2. Полином информационных символов К(Х) за счет подачи на,- К выход регистра умножается на ХХ , где 4 - число проверочных симво:ов. Б устройстве для кодирования осуществляется деление К(Х)Х на,54полином 8(х) = х + ( Ф- + 1) х +х +. Деление заканчивается54 219 ткак только иинформационных символов поданы на входы 13, в результате чего в регистре сдвига, составленном из буферных регистров 5-8, получен остаток г(Х) = г Х + г Х +г + г,Х + г,. После этого блоки 4 и 12 по первым информационным входам закрываются, а по вторым открываются управляюЩим сигналом Т 2 на входе 16.11 роверочкые элементы нз регистров 5-8 выводятся вслед за информационными элементами. Таким образом, закодировано сообщение, имеющее длину и байтов.Умножители 1 и 2 производят умножение на соответствующие постоянные219 54элементы поля , и Ж , обеспеЧивая режим деления на полином 8(Х), Они строятся на основе сумматоров по модулю два и сгруппированы так, что четыре двухвходовых сумматора можно построить на основе одной микросхемы типа К 155 ИП 2, а остальные схемы - на микросхемах типа К 155 ПП 5.Б предлагаемом устройстве на два умножителя и на один блок сумматоров по модулю два меньше и ка один блок инверторов больше, чем в известном.Таким образом, предлагаемое устройство для кодирования по сравнению с известным за счет исключения двух умножителей и блока сумматоров по модулю два обладает более высокой надежностью.Ф о р и у л а изобретенияУстройство для кодирования, соцержащее первый буферный регистр, выходы которого подключены к первым5 10 15 20 25 30 35 40 45 ра. входам первого блока сумматоров помодулю два, выходы которого соединены с информационными входами второго буферного регистра, выходы которого подключены к первым входамвторого блока сумматоров по модулюдва, выходы которого соединены синформационными входами третьего буферного регистра, четвертый буферный регистр, выходы которого соединены с первыми входами третьего блокасумматоров по модулю два, вторыевходы которого объединены с соответствующими первыми информационнымивходами блока ключей и являютсяинформациакными входами устройства,выходы третьего блока сумматоров помодулю два подключены к вторым информационным входам блока ключей иинформационным входам блока элементов И, выходы которого через первыйи второй умкожители соединены соответственно с информационными входамипервого буферного регистра и вторыми входами второго блока сумматоровпо модулю два, входы синхронизациипервого - четвертого буферных регистров объединены и являются входомсинхронизации устройства, управляющий вход блока элементов И объединенс первым управляющим входом блокаключей и является первым управляющимвходом устройства, второй управляющий вход и выхОды блока ключей являются соответственно вторым управляющим входом и выходами устройства, отличающееся тем,что, с целью повышения надежностиустройства, в него введен блок элементов НЕ, входы и выходы которогоподключены соответственно к выходамвторого умножителя и вторым входампервого блока сумматоров по модулюдва, выходы третьего буферного регистра соединены с информационнымивходами четвертого буферного регист 1390801