Устройство для умножения в конечныхпОляХ Советский патент 1981 года по МПК G06F7/49 

Изобретение относится к построению кодирующих и декодирующих устройств корректирующих циклических к дов, предназначенных для передачи сообщений с высокой достоверностью в системах доставки и обработки дис ретной информации. Известно устройство для умножения полиномов, содержащее первый, второй и третий сумматоры по модулю два, элемент задержки, регистр, вхо которого соединен со входом устройства и с первым входом второго сумматора, выход которого соединен со вторым входом второго сумматора и со входом элемента задержки, выход которого соединен с первым входом третьего сумматора, а выход - является выходом устройства для умножен полиномов 1 . Недостаток этого устройства сос-г тонт в том, что умножение возможно лишь на фиксированный полином. Известно устройство для умножения, содержащее блоки сумматоров по модулю два, ячейки регистра, блоки умножения первой и второй групп, пр чем вход устройства соединен со вхо дами блоков умножения первой группы выходы которых соединены с первьвли входами блоков сумматоров соответственно, вторые входы которых соединены соответственно с выходами соответствующих блоков умножения второй группы, входы которых, кроме последнего, соединены между собой, а также с выходом устройства и выходом последнего блока умножения Еторой группы, выход каждого блока сумматора, кроме последнего, соединен со входом соответствующей ячейки регистра, выход каждой ячейки регистра соединен с третьим входом соответствующего блока сумматоров, выход последнего блока сумматоров соединен со входом последнего блока умножения второй ; группы 2. Недостаток этого устройства состоит в том, что умножение в конечных полях данным устройством производится только лишь на фиксированный полином. Наиболее близким по технической сущности к предлагаемому является устройство умножения в конечных полях, содержащее ячейки первого, второго и третьего регистра, сумматоры по модулю два первой и второй группы, элементы И, элементы ИЛИ первой и второй групп, блоки умножения, причем первая группа выходов устройства соединена соответственно с первыми входами элементов ИЛИ первой группы, выходы которых соединены соответст.венно с первыми входами соответствующих ячеек первого регистра, выходы ячеек первого регистра, за исключением последней, соединены соответственно со вторыми входами соответствующих эле.ментов ИЛИ первой группы выход последней ячейки первого регистра соединен со вторым входом соответствующего элемента: ИЛИ первой группы и с первыми входами элементов И, выходы которых соединены с первым входами сумматоров первой группы, выходы которых соединены со входами ячеек.третьего регистра соответствен но, а вторые входы - с выходами ячеек третьего регистра и с выходами устройства соответственно, вторые вх ды элементов И, кроме последнего, со динены с выходами ячеек второго регистра и с первыми входами вторых су сумматоров соответственно, второй вход последнего элемента И соединен с выходомпоследней ячейки второго р гистра со входом первого элемента ИЛ второй группы, и со входами блоков умножения, выходы которых соединены соответственно со вторыми входами соответствующих сумматоров второй группы, выходы которых, соединены с первыми входами соответствующих элементов ИЛИ второй группы, вторые вхо ды которых соединены со входами уст«ройства второй группы, а выходы - со входами ячеек второго регистра З. Недостатком является избыточность элементов устройства. Операцию умнож нию реализуют более простым методом, используя схему для одновременного умножения полиномов сомножителей и д ления на образующий полином поля. Из быточность элементов устройства снижает надежность в целом. Цель изобретения - упрощение устройства. Указанная цель достигается тем, что в устройство для умножения в ко.нечных полях, содержащее первый, вто роЩ и третий регистры, блоки умножения и группу элементов И, причем пер вая группа входов устройства соединена с разрядными входами первого регистра, выход последнего разряда которого соединен со входом его первого разряда и с первыми входами элементов И группы/ выход последнего разряда второго регистра соединен со входами блоков умножения, каждый раз ряд второго регистра содержит су1лматор по модулю два и триггер, первый вход сумматора по модулю два каждого разряда второго регистра соединен с выходом соответствующего элемента И группы, второй вход сумглатора по модулю .два первого разряда второго регистра соединён с выходом его последнего разряда, а второй вход сумматора по модулю два j-ro разряда второго регистра (, ..., э, где а разрядность регистра) соединен с выходом j-1-го блока умножения, вторая группа входов устройства соеди.нена с входами разрядов третьего регистра, тактовый вход устройства соединен с тактовыми входами первого и второго регистров, выходы разрядов третьего регистра подключены ко вторым входам элементов .И группы, выходы триггеров второго регистра, являющиеся выходами соответствующих разрядов второго регистра, подключены к группе выходов устройства, третий:вход сумматора по модулю два каждого разряда второго регистра, начиная со второго,соединен с выходом триггера предыдущего разряда второго регистра. На чертеже представлена функциональная схема устройства. Устройство содержит регистры 1, 2 и 3, причем регистры 1 и 2 являются сдвиговыми, тактовый вход 4, блоки 5 умножения, элементы И 6, 6q, входы 7 :, Sg, выходы 9, Каждая i-я ячейка регистра 1 содержит элемент ИЛИ 10 и триггер 11 (i-1, ...,а). Каждая 1-я ячейка регистра 2 Содержит сумматор 12 по два и триггер 13, причем сумматор 12| по модулю два первой ячейки является двухвходовым, а сумматоры 122, ..., 12а последующих ячеек трехвходовыми, образованных например, последовательным соединением двух двухвходовых сумматоров 14 и 15 по модулю два. Каждая 2-я ячейка регистра 3 содержит триггер 16 (где а разрядность регистров 1, 2 и 3). Входы 7, .. . ., 7г5( устройства соединены соответственно с первыми входами элементов ИЛИ 10, ..., 10 регистра 1, выходы которых соединены соответственно со входами соответствующих триггеров 11, а регистра 1, тактовые входы триггеров 11, ..., HQ регистра 1 соединены с тактовым входом 4 устройства и с тактовыми входами триггеров .13, ..., 13д регистра 2, выход триггера 11. регистра 1 соединен со вторым входом элемента ИЛИ 1й( , выход триггера llg регистра 1 соединен со вторым входом элемента .ИЛИ 10 и с первыми входами элементов И 6, бд вторые входы которых соединены с выходами триггеров 16, ..., 1ба регистра 3, входы которых соединены с входами 8о1 устройства умножения. вь1ходы элементов &., ..., 6 соединены со входами сумматоров 12, ..., 12(., по модулю два, выходы триггеров 13а регистра 2 соединены соответственно с выходами 9 устройства умножения и со вторыми ухо.ц, со;.- -1-ветствующих сумматоров , ..., 12д регистра 2 соединен со входами блоков 5, ..., 5 умножения и со вторым, входом сумматора 1.2j выход которого соединен со входом соответствующего триггера 13 регист ра 2, выходы блоков 5, -, S, , ум ножения соединены соответственно вто рь-ми входами сумматоров 12, ..., 12 по модулю два, третьи входы которых соединены с выходами соответствующих триггеров 13,..., 13„ , регист ра 2. - При описании работы устройства рассматривают поле GF (2а ), Определяемое многочленом F(x) степени, а коэффициентами из поля GF(2), т.е. .F(x)... F.&GF(i),r-o,..,a-i- Каждый элемент FG(2) представляют в виде многочлена над GF(2), степень которого меньше а, т.е. вместо элеме тов p,g,r e.GF(2) рассматривают мно гочлены р(х), д(х) и z(x), соответствующие этим элементам . Р(и) -- S р х ), --o,..,o g(x s gr-eoFti), ,..., )2V;X r-eGFC2V, ,...,0--) Тогда умножение элементов GF(2),. т.е. pg r выполняется no. правилам умножения .представляющих эти элементы многочленов по модулю F(x), т.е. р(х) g(x)r(x) mod F (х) , r(x)p(x). . g (x)-4-b(x) F (х) ,| где b(x - полином степени меньшеГ, чем а-1.. . Поскольку eGF(2), , ..., а-1 то блок умножения НУ, осуществляющий умножение на F , ...г а-1, реализуется наличием связи, если F.., либо отсутствием связи, если . Работает устройство умножения в конечных полях следунвдим образом. В исходном состоянии ячейки регистров 1, 2-й 3 находятся в нулевом состоянии. На входы 7 , . .., Tj,, устройства, подаются одновременно в порядке возрастания индексов коэффициенты много члена д(х), т.е. на вход 7 - коэффициент дд, на вход - коэффициент д. на вход 7 - коэффициент д Причем 9 соответствует единичный потенциал на входе 7.,, а д - 0-нулево потенциал на входе 1 . Аналогичным образом на входы 8. , ..., 8ц устрой ства подаются коэффициенты многочлена р{х) и запоминаются в регистре 3. Затем на тактовый вход 4 поступают импульсы тактового генератора (на чертеже не показан). На первом такте коэффициенты многочлена g(x) записываются в регистр 1. При этом на выходе триггера HQI регистра 1 появляется коэффициент gQ, который поступает На первые входы элементов И 6j,.,. i.., 6g, на вторые входы которых поступайт коэффициенты полинома р(х) выходов регистра 3. в результате на входы триггеров 13, ..., LЭ. посгупают через элементы И сумматоры 12, ..,, 12q коэффициенты полинома д. р(х). На втором такте полином g р(х) записывается в триггеры 13, ..., 13q регистра, а на входы сумматоров 12, ..., 12а по модулю два поступают коэффициенты полинома да-ч р(х). В результа1те на выходах сумматоров .14 появляются коэффициенты полинома gr.xp(5i)©gr.,p(4l-.(8.,K,,-)pU) которые.поступают на входы сумматоров 15, на входы которых поступают коэффициенты полинома bj,|,j F(x), где Ь0. если ,в триггере 13о, записана 1, и , если записан 0. . . Таким образом, на входах триггеров 13, ..., 13а появляются коэффициенты полинома (да--( Qct-d Р На третьем такте полином (.x -v ц.д ,j)p(x)+bc,(x) записывается в триггере 13, ..., , а на входах соответствующих триггеров формируются коэффициенты полинома fe-1 ia-(i) a-3Pt V/ -fc-i - 8 а-2 а-з)р 0,-а ViJf Таким образом, на i-м такте (i 2, ..., а+1) содержимое регистра 2 умножается на х по модулю F(x) исуммируется с полиномом 9(4 р(х), т.е. на i-м т.акте в регистре 2 записан полином ( «-iM) . J-4 в результате на а+1-м такте в регистре 2 аписан полином (е а-1 Ча-2 -е-,) )( g(J.7pUUb(x)FtX) HU1 , который появляется .на выходах 9 , ... 9с| устройства для умножения. Таким образом сформирован результат умножения двух полиномов. Эффективность предлагаемого устройства по отношению к известиому оп