Устройство для деления многочлена на многочлен Советский патент 1982 года по МПК G06F7/52 

(54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ МНОГОЧЛЕЬи НА МНОГОЧЛЕН Изобретение относится к области передачи данных и может быть использовано в устройствах защиты от ошибок и в устройствах фазирования аппаратуры передачи дискретной информации. Известно устройство для деления многочлен на многочлен, используемое для вычисления синдромов циклического кода 1 . Однако зто устройство пригодно для обработки только двоичной информации. Наиболее близким по технической сущности к данному изобретению является устройство, содержащее г элементов задержки, (г-1) сумматоров, г+1 умножителей (где г - степень многочлена делителя), причем выход i-ro элемента задержки соединен с первым входом j-ro сумматора (где i 1,. . . , г - 1, j 1,.. г-1), выход j-ro сумматора соединен с первым входом а-го злемента задержки (где а 2,. . . г), выход г-го злемента задержки соединен с входом (г+1)-го умножителя, выход которого сое динен с входами г умножителей, выход Ь-го умно жителя соединен с вторым входом j-ro сумматора (где b 2г) 2. Недостатком известного устройства является значительное время определения остатка и тем большее, больше степень п делимого многочлена, что не позволяет применять устройство в параллельных системах фазирования. Цель изобретения - повышение быстродейсг;Поставленная цель достигается тем, что в устройство введены г сумматоров, г умножителей, блок и регистр сдвига, причем выход первого умножителя соединен с первым Bfходом первого элеметгга задержки, информационный вход регистра сдр.ига подключен к входу устройства, выход с-го злемента задержки соединен с первым входом d-ro сз мматора (где , . . ., г, d г, . . ., 2г - 1), второй вход которого соединен с выходом k-го-умножителя (где k г + 22г + 1), выходы m сумматоров соединены соответственно с вторыми входами г злементов задержки (где т- г, ... ., 2г-1) и подключены соответственно к выходам устройства, выход младшего разряда регистра сдвига соединен с третьим входом г-го сумматора, разрядные выходы регистра 395 сдвига соединены соответственно с первыми входами k умножителей, вторые входа KOTOpfcix соединены соответственно с выходами блока памяти, На чертеже показана схема устройства. Устройство содержит элементы li - ly. задер жки, сумматоры 2|-2j- j , умножителя 3i , сумматоры 4i - 4 умножители 5| 5у, блок 6 памяти, регистр 7 сдвига. В устройстве выход элемента задержки соединен с первым входом 2 -го сумматора (где i 1,. . ., г - 1, j 1 . . . . ., г -1 ), выход 2 j-ro сумматора соединен с первым входом элемента 1 а-го задержки (где, а 2, . , ,, г), выход элемента 1 задержки соединен с входом 3j. -го умножителя, выход которо го соединен с входами умножителей ,, выход 3 Ь-го умножителя соединен; с вторым входом 2 j-ro сумматора, (где b 2,..., г), выход умножителя 3j соединен с первым входом элемента It задержки, информационный вход регистра 7 сдвига подключен к входу устройства, выход 2 с-го элемента задержки соединен с первым входом 4 d-ro сумматора (где с 1, . . ., г, d г,..., 2 г -1) , второй вход которого соединен с выходом 5 k-ro умножителя (где k г + 2, . . ., 2 +1), выходы сумматоров 4i - 4 у, соединены соответственно с вторыми элементами 1| - Ij. задержки и подключены соответственно к выходам устройства, выход младшего разряда регистра 7 сдвига соединен с третьим входом сумматора 4i, разрядные выходы регистра 7 сдвига соединены соответственно с первыми входами умножителей 5i - 5у«, вторые входы которых соединены соответственно с выходами блока 6 папяти. Це1ш передачи импульсов на чертеже не показаны. Количество элементов 1 j - 1 - задержки и количество сумматоров 4i - 4 j равно степени делителя, количество) умножителей 3i - и сумматоров 2i - 2(/. зависит от вида делителя, количество умножителей 5i - SY зависит от вида производящего полинома кода и длины кодовых комбинаций (от вида делителя и степени делимого). Устройство работает следующим образом. Вычисление в каждом j-ом такте остатка Ri QT, деления многочлена Q . (х) на много член F (х) получается однотактным сдвигом по элементам задержки вычисленного в предыдущём такте остатка . поразрядного суммирования сдвинутого остатка R v с многочленом, записанным в ПЗУ, поразрядно умноженным на коэффициент старшего разряда, многочлена (х) и Последующим прибавлением к полученной сумме младщего разряда многочлена Q (х), т. е. требуется выполнить всего четыре операции, некоторые из которых могут выполняться параллельно, причем число операций не зависит от степени делимого. Действительно, если имеется принимаемая последовательность Cji.i,On-l,i,Oio м ау,..,,(,С5|,01о и допустимо, что известен остаток Rj (х) от деления многочлена Q ii)-a;.,x4a;,., )(:;:;;,-« а о на многочлен F (X), то остаток Ri (X) от деления многочлена РаСх а„-х - а; х 2. п-ъ а х -аоХ -ау,- , F (X) равен на многочлен г.)-К..:,.. а1,Дс1дХ- -аи-1 VModgr(x; 1ау,.. а„.,, -... а, х сзоX tOy,.,,-а„ F(X) Ix(av,. y,.Tk --( 01д)-Юи.-а„. F(x)хй,(х)и-1-аи-. f, где - mod F (х). ii -J(. Так как величина | X ) при передаче информации укороченным циклическим кодом представляет собой какой-то определенный многочлен степени меньше г, то каждый последующий остаток определяется предыдущим остатком, младшим разрядом делимого многочлена и старшим разрядом предыдущего делимого многочлена. Таким образом, устройство вьшрлянет функ-. цин определения остатка при делении многочлена многочлен, при этом требуется незначительное количество операций, независящее от длины делимого многочлена, т. е. увеличивается .быстродействие по сравнению с прототипом. Формула изобретения Устройство для деления многочлена на мгогочлен, содержащее г элементов задержки, (г - 1), сумматоров, (г + 1) умножителей (где г - степень многочлена делителя), причем выход i-го элемента задержки соединен с первым входом j-ro сумматора (где i 1,. ... г - 1, j 1, . . ., г - 1), выход J-ro сумматора соединен с первым входом а-го элемента задержки (где а 2. . . ., г), выход г-го элемента задержки соедин ен с входом (г+1) умножителя, выход которого соединен с входами г умножителей, выход Ь-го умножителя соединен с вторым входом j-ro сумматора (где .,. .. г), отличающееся тем, что, с целью повышения быстродействия, в него введены г сумматоров, г уулножителей, блок памяти и регистр сдвига, причем выход -первого умножителя соединен с перпьш входом первого элемента задержки, информационный вход регистра сдвига подключен к входу устройства, выход с-го элемента задераски соединен с первым входам d-ro сумматора (где с 1, . . г , d р г. , . 2 г - 1), второй вход которого соединен с выходом k-ro умножителя (где k г 2, -, . , , 2 г + I), выходы m сумматоров соединены соответственно с вторыми входами г элементов эаяерж91си (где m - г .... 2 г - 1) и подключены соответственно к выходам устройства, выход младшего разряда регистра сдвига соединен с третьим входом г-го сумматора, разрядные выходы регистра сдвига соединены соогветаг венио с первыми входами k умножителей, вторые входы соединены соответствен но с выходами блока памяти. Источники информации, принятые во внимание при экспертиз 1.Авторское свидетельство CCCPN 710040, кл. G 06 F 7/52, 1975. 2.Питерсон У., Уэлдон Э. Коды, исправл варщие ошибки. М., Мир, 1976, с. 199-200 (прототип).

f л.

tt t