Устройство для кодирования Советский патент 1986 года по МПК H03M13/51 

ю

СП М Изобретение отнрсится к вычислительной технике и может использоваться в системах передачи цифровой информации с обнаружением и исправлением групповых ошибок. Цель изобретения - повышение быст родействия и надежности функциониро зан 1я. На фиг. 1 изображена блок-схема устройства для кодирования; на фиг. 2 4 - функциональные схемы соответственно формирователя первого проверочного символа, формирователя последующего проверочного символа и блока управления; на фиг. 5 - временные .диаграммы сигналов. Устройство для кодирования содержит сдвиговый регистр 1, основной элемент И 2, блок 3 управления, формирователь 4 первого проверочного символа, 2t - 1 формирователей Ь последующего проверочного символа, 2t дополнительных элементов И 6, элемент ИЛИ 7, информационный и тактовый входы 8 и 9 и выход 10. Здесь t - число ошибок, исправляемых выход ным кодом устройства над полем GF(2 Регистр 1 содержит 2т разрядов, выхо ды m первых его разрядов подключены к информационным входам блоки 3 управления и формирователя 4. Формирователь 4 первого проверочного символа содержит (фиг. 2) первы второй и третий буферные регистры 11-ТЗ, вычитатель 14, преобразователь 15 кода, сумматор 16 и регистр 17 сдвига. Формирователь 5 последующего про верочного символа содержит (фиг. 3) вычитатель 18, преобразователь 19 кода, первый и второй буферные регистры 20 и 21, сумматор 22и регист 23 сдвига. q. Блок 3 управления содержит (фиг. счетчик 24, дешифратор 25, три элемента ЗАПРЕТ 26, первый элемент И 2 и 2t+1 вторых элементов И 28, инфор мационные входы 29, выходы 30-40 с первого по (2ь+9)-й. Буферные регистры 11 - 13 формирователя 4 и буферные регистры 20 и 21 формирователя 5, а также регистры 17 и 23 сдвига формирователей 4 и 5 имеют по m разрядов. Преобразователи 15 и 19 кода формирователей 4 и 5 осуществляют над входной величиной Z преобразование 1©oL , где oL 6 GF (2) - примитивный элемент поля GF(2), © - сложение по модулю два. Вычитатели 14 и 18 и сумматоры 16 и 22 формирователей 4 и 5 осуществляют соответствующие операции по модулю 2 -1. Первые входы вычитателя 18 каждого -го формирователя 5, где 1 1, 2t-1, являются информационными входами формирователя 5, вторые входы вычитателя 18 при этом соединены с шинами источников логических уровней в соответствии с двоичным кодов номера данного формирователя 5. На фиг. 5 показаны следующие сигналы: а - тактовые импульсы на тактовом входе 9, также на первом выходе 30 блока 3, б - к - сигналы на выходах 31-39 соответственно с второго по девятый блока 3, л и м сигналы на выходах (2t-1)-ro и (2t)-ro элементов И 28 блока 3, т.е. на (2t+7)-M и (2t+8)-M выходах этого блока 3, н - сигнал на (2t+9)-M выходе 40 блока 3 управления. Принй ип действия устройства для кодирования заключается в следующем. Информация, подлежащая кодировайию, разбивается на блоки по т-разрядных символов в каждом, являющихся показателями степени примитивного элементаЫ СР(2) - корня непроводимого многочлена степени т. Обозначим информационные символы К;, ,...,2 - 2, проверочные символы К., j ,..., 2(t-1), где t число исправхеяемых кодом ошибок. Тогда первый проверочный символ получается из соотношения / --1:ы сс ®о1 ©.. ©ot ® и f - суммирование в поле GF(2 }. Введем функцию tf (2) такую, что ( 1 .. Тогда. 01 ct (1 1 (. Тогда + -1 oL- и ® ) oL l- }t°-4 °. ДалееЫ% @ oL И В общем случае: ./ (o-,., или, переходя к показателям степеней: а. К.+.ч(а..- К.). Обозначим b; .а..- К., тогда К, +4 (Ь..,) Ь, K,-K. + .f (Ь.,), откуда Уравнение (2) является итерационной формулой для получения первого проверочно1 о символа. Начальные условия: Ь, К.- К I .р , 1 Вычисление по формулам (2) и-(3) т.е. операции сложения и вычитание по модулю 2-1. При эт осуществляют в виду, что К.. 2 - 1 нужно иметь определено в кольце по модулю 2 не Поэтому ()ta mm где а ,„- любой элемент кольца. При О и Kj 2 - 1 изымаются этом oL из суммы (1). Для учета этой ситуадщи в устройство введен элемент И 2 .фиг. 4), выдающий запрет на выдачу управляющих сигналов с блока 3 управления.. Остальные -е проверочные симво лы получают из соотношения: .ol« °®c где П 1,...,2t-1. Аналогично формуле (2) получим: Ъ. K.+ (i-D-K.-n i +M(b,) . К. + (ъ1) (5) Начальные условия: Ь К -К - (6 Окончательный результат по форму лам (1) и (4) получается на такте (i ). В-этом такте форм лы (2) и (5) примут вид: V.. V:r Устройство для кодирования работает следующим образом. (На фиг. 5 представлена временная диаграмма ра боты устройства при и t 7). На вход 9 устройства поступают блоки информации по 60 разрядов в сопровождении тактовых импульсов (фиг, 5), затем 56 тактов следует пауза для заполнения ее проверочными символами. Первые 4 такта следует 0-й цикл, в течение которого заполняются первые 4 разряда сдвигового регистра 1, содержащего в рассматриваемом примере восемь разрядов. Затем следует 1-й цикл (5,6,7,8 такты), где по сигналу с второго выхода 31 блока 3 (фиг.,,56) производится запись на регистр 11 первого символа информации и затем по сигналу с выхода 32 блот ка 3 (фиг. 56) - его перепись с регистра 11 на регистр 12. В следующем, втором цикле (9, 10, 11, 12 такты), производится вычитание из содержимого (К) регистра 12 записанного в регистре 11 второго (К) информационного символа на вычитателе .14, сложение полученного результата с нулем регистра 13 на сумматоре 16 и запись результата на регистр 17 по сигналу с выхода 33 блока 3 (фиг. 5г). Одновременно по сигналу с выхода 35 блока 3 (фиг.5 результат вычитания с вычитателя 14 через вторые выходы формирователя 4 первого проверочного символа поступает на информационные входы формирователей 5 последующего проверочного символа, в которых на вычитателях 18 производится вычитание номера 1 формирователя 5 и запись полученной разности на регистр 20. По сигналу с выхода 32 блока 3 . роизводится перепись на регистр 12 торого (К,) информационного симвоа, а по сигналу с выхода 34 блока (фиг. 53) - передача содержимого егистра 17с преобразованием его в реобразователе 15 кода в регистр 13. Одновременно по сигналу с рыода 37 блока 3 (фиг. 5) произвоится сложение на сумматоре 22 соержимого регистра 20 с нулем регитра 21 и запись результата на реистр 23. Третий цикл аналогичен второму а исключением того, что при сложеии на сумматорах 16 и. 22 оба опеанда в общем случае отличны от нуя, и по сигналу с выхода 36 блока (фиг.5з1 осуществляется передаа содержимого регистра 23 с преобразованием в преобразователе 19 кода в регистр 21. Циклы с 4-го по 15-й аналогичны третьему. При этом в 15-м цикле после передачи содержимого регистра 11 на регистр 12 регистр 11 обнуляется. Далее, в 16-м цикле по сигналу с выхода 33 блока 3 на вычитателе 14 из содержимого регистра 12 вычитаетс нуль регистра 11 (формула 2 ) и реэультат (содержимое регистра 12) на сумматоре 16 складывается с содержимым регистра 13. Результат сложения, являющийся первым проверочным символом, записывается на регистр 17. Одновременно с вычитателя 14 информация поступает на вычитатель 18, где производится вычитание величины - h()(-(2 -2))Ч -f|, так как -() ()-() 1. По сигналу с выхода 35 блока 3 результат вычитания записывается на регистр 20. Одновременно, по сигналу с выхода 36 блока 3 производится перепись содержимого регистра 23 (от предьщущего цикла) на регистр 21с преобразованием в преобразователе 19. И, наконец, на сумматоре 22производится сложение содержимого регистров 20 и 21. Результат сложения, являющийся I +1- проверочным символом, записывается на регист 23по сигналу с вьпсода 37 блока 3. В каждом цикле работы устройства на элементе И 27 производится анали очередного символа. Если анализируе мый символ равен ИИЧ ), то в блок 3 управления элементы ЗАПРЕТ 2 запрещают вьщачу сигналов с вькодов 32-34 блока 3, при.этом обнуляется регистр 11. Начиная с 2-го цикла и до конца 16-го цикла по сигналу с выхода 38 блока 3 (фиг. StfJ производится выдача информационных символов с перiBoro выхода сдвигового регистра 1 через основной элемент И 2 и элемен ИЛИ 7 на выход 10 устройства. В 17 дакле по сигналу с выхода 39 блока 3 (фиг. 5к) аналогично производится вьщача первого проверочного символа в 18-м цикле - второго проверочного символа и т.д. по сигналу с выхода 40 блока 3 (фиг. 5 ) четырнадцатого проверочного символа. Начало вьщачи тринадцатого проверочного символа совпадает с началом обработки следу щего блока информации. Таким образом, представление инормации в виде показателей степени римитивного элемента ct поля GF(2 ), вляющегося корнем неприводимого ногочлена степени т, дает возможость свести получение проверочных имволов в операциям сложение и выитание, что позволяет повысить наежность устройства и его быстродейтвие. ормула изобретения 1. Устройство для кодирования, содержащее сдвиговый регистр, основной элемент И и блок управления, тактовый вход которого является тактовым входом устройства, первый выход блока управления соединен с управляющим входом сдвигового регистра, информационньй вход которого является информационным входом устройства, а выход последнего разряда соединен с первым входом основного элемента И, отличающееся тем, что, с целью повышения быстродействия и надежности функционирования, в него введены фор 1ирователь первого проверочного символа, 2t-1 формирователей последующего проверочного символа, 2t дополнительных элементов И и элемент ИЛИ, выход которого является выходом устройства, а входы соединены с выходами основного и дополнительных элементов И, первый вход первого дополнительного элемента И подключен к первому выходу формирователя первого проверочного символа, информационные входы которого объединены с информахщонными входами блока управления и подключены к выходам ш первых разрядов сдвигового регистра, общее число разрядов которого 2т, выходы блока управления с второго по пятый подключены к управляющим входам соответственно с первого по четвертьй формирователя первого проверочного символа, вторые выходы которого соединены с соответствующими информационными входами формирователей последующего проверочного символа, выходы которых подключены к первым входам дополнительных элементов И с второго по 2t-и, первые, вторые и третьи управлякяцие входы формирователей последующего проверочного символа соответственно объединены и подключены к шеетому, седьмому и восьмому выходам блока управления, выходы которого с девятого по (2с+9)-й соединены с вт рыми вхйдами соответственно основного и дополнительных элементов И с первого по 2t-H, где t - число ошибок, исправляемых выходным кодом устройства над полем GF(2 ). 2.Устройство по п. 1, о т л ич а ю щ-е е с я тем, что формирователь первого проверочного символа выполнен на первом, втором и третьем буферных регистрах, вычитателе, сумматоре, преобразователе кода и регистре сдвига, выход последнего разряда которого является первым выходом формирователя первого проверочного символа, информационные входы первого буферного регистра являются информационными входами формирователя первого проверочного символа, выходы первого буферного регистра подключены к соответствующим первым : входам вычитателя и информационным входам второго буферного регистра, .выходы которого соединены с соответствующими вторыми входами вычитателя, выходы которого, являющиеся вторыми выходами формирователя первого проверочного символа, подключены к соответствующим первым входам сумматора, выходы которого подключены к соответствующим информационным входам регистра сдвига, выходы-которого соединены с соответствующими входами преобразователя кода, выходы которого подключены к информацион ным входам третьего буферного регист ра, выходы которого соединены с соот ветствующими вторыми входами суммато ра, управляющие входы первого и второго буферных регистров, регистра сдвига и третьего буферного регистра являются управляющими входами соответственно с первого по четвертый формирователя первого проверочного символа. 3.Устройство по п. 1, о т л ичающееся тем, что каждый й формирователь последующего проверочного символа, где 1, 2t-1, выполнен на первом и втором буферных регистрах, вычитателе, сумматоре, преобразователе кода и регистре сдви га, выход последнего разряда которого является выходом формирователя последующего проверочного символа, первые входы вычитателя являются информационными входами формирователя последующего проверочного символа вторые входы вычитателя соединены с шинами источников логических уровней в соответствии с двоичным кодом номера , выходы вычитателя подключены к соответствующим информационным входам первого буферного регистра, выходы которого соединены с соответствующими первьми входами сумматора выходы которого подключены к соответствукнцим информационным входам регистра сдвига, выходы которого соединены с соответствующими входами преоб азователя кода, выходы которого подключены к информационным входам второго буферного регистра, выходы которого соединены с соответствующими вторыми входами сумматора, управляющие входы первого, буферного регистра, регистра сдвига и второго ; буферного регистра являются соответственно первым, вторым и третьим управляющими входами формирователя последующего проверочного символа, 4, Устройство по п. 1, отличающееся тем, что блок управления выполнен на дешифраторе, первом элементе И, 2t+1 вторых элементах И, трех элементах ЗАПРЕТ и счетчике, счетньй вход которого объединен с первьми входами вторых элементов И и является тактовым входом блока управления , выходы счетчика подключены к входам дешифратора, первый .и второй выходы которого являются соответствующими выходами блока управления, третий, четвертый и пятый выходы дешифратора соединены с разрешающими входами соответственно первого, второго и третьего элементов ЗАПРЕТ, запрещающие входы которых объединены и подключены к выходу перврго элемента И, входы которого явяются информационными входами блока управления, выходы первого, второго третьего элементов ЗАПРЕТ и шестой, седьмой и восьмой выходы дешиф-ратора являются выходами блока управления соответственно с третьего по восьмой, выходы дешифратора с девятого по (2t+9)-и подключены к вторым входам вторых элементов И соответственно с первого по (2с+1)-й выходы которых являются выходами блока управления соответственно с девятого по (2t+9)-й.

w

Изобретение относится к вычислительной технике. Его использование в системах передачи цифровой информации с обнаружением и исправлением групповых ошибок позволяет повысить быстродействие и надежность функционирования. Устройство для кодирования содержит сдвиговый регистр, основной элемент И и блок управления. Введение формирователя первого проверочного символа, 2t-1 формирователей последукщего проверочного символа, 2t дополнительных элементов И и элемента ИЛИ,- где t - число ошибок, исправляемых выходным кодом устройства над полем GF

Фиг. 2

ч Ь

19

СлО

Фиг.З

о цикл Щикл 2UUK/J 3 цикл 15 цикп 16 U,UK/I г7цик/1 28цикл t , If 5. В 9 1213 15 57 60 SI 6465 .68 tl 120