4. Реализация операций умножения и деления многочленов в поле двоичных чисел

Операции умножения и деления многочленов реализуются с помощью регистров сдвига, состоящих из сумматоров, запоми­нающих устройств и устройств умножения. Сумматор (рис. 1.1, а) представляет собой устройство, осуществляющее сложение по модулю 2 величин на входах 1 и 2. Запоминающее устройство (рис. 1.1,6) служит для хранения в течение определенного вре­мени постоянной величины а.

Рис. 1.1. Функциональное обозначение сумма­тора по модулю два (а), запоминающего уст­ройства (б) и устройства умножения (в)

Устройство умножения (рис. 1.1, в) осуществляет умноже­ние некоторой входной величины с на постоянный множитель а.

Умножение многочленов

Умножение некоторого произвольного многочлена f₁ (х) = = а₀ +a₁x+…+a_n-1x^n-1+a_nxⁿ на фиксированный много­член f₂(х)=b₀+b₁x+…+b_k-1x^k-1+b_kx^k осуществляет­ся с помощью регистров сдвига, изображенных на рис. 1.2. Эти регистры строятся по виду многочлена f₂ (x) и отличаются лишь расположением сумматоров. Предполагается, что регистр пер­воначально находится в нулевом состоянии. На вход регистра поступают коэффициенты многочлена f₁ (x). начиная со стар­шей степени, а затем следуют k нулей.

Схема, изображенная на рис. 1.2, а и представляющая со­бой регистр с вынесенными сумматорами, работает следующим образом. Когда на входе имеет место первый коэффициент а_п, то на выходе появляется первый коэффициент произведения f₁(x)f₂(x), равный a_nb_k. Кроме того, коэффициент а_n запоми­нается в первой ячейке памяти регистра. Со вторым тактом на входе появляется коэффициент a_n-1 и записывается в первую ячейку памяти, а коэффициент а_n этим же тактом переписыва­ется из первой во вторую ячейку регистра. При этом на выходе схемы появляется значение второго коэффициента произведения f₁(x) f₂ (x), равное (а_п-1 b_k+ a_n b_к-1 ) и так далее.

Таким образом, схема работает в соответствии с таблицей.

Следовательно, произведение будет равно:

Схема, изображенная на рис. 1.2,6 и представляющая со­бой регистр с встроенными сумматорами, работает аналогично предыдущей. Очевидно, что обе схемы равноценны.

выход

Рис. 1.2. Реализация умножения многочленов с помощью регистров сдвига с вынесенными (а) и встроенными (б) сумматорами

Рассмотрим некоторые характерные особенности построения этих схем для многочленов с двоичными коэффициентами, а именно с коэффициентами 0 и 1.

Умножение на величину b_i производим по правилу:

Для b_i= 0 :a_jb_i=a_j0=0,

и для b_i=1:a_jb_i=a_j*1=a_j,

Таким образом, умножение на 0 соответствует разорванной цепи, а умножение на 1 — короткому замыканию.

Пусть, например, f₂ (X) = 1 + х+ х³ +x⁵, т. е. b₀= 1, b₁= 1,

b₂=0,b₃=1,b₄=0,b₅=1.

Рис. 1.3. Устройство умножения на многочлен f (x) = 1 + х + x³ + х⁵

Схема умножения на многочлен реализуется с помощью ре­гистра с встроенными сумматорами, имеющего вид, представ­ленный на рис. 1.3. Как видно из рис. 1.3, сумматор, на который подан только один вход, может быть устранен.

Аналогично строится регистр с вынесенными сумматорами.

Деление многочленов

Операция деления многочленов может быть реализована с помощью регистра сдвига с обратными связями. Схема деле­ния произвольного многочлена f₁(х) = a₀+a₁x+…+a_n-1x^n-1+a_nxⁿ на постоянный многочлен f₂ (х)= b₀+b₁x+…+b_k-1x^k-1+b_kx^k представлена на рис. 1.4.

Рис. 1.4. Реализация деления на многочлен с помощью регистра сдвига c обратными связями

До поступления многочлена f₁ (x) на вход схемы, запоминаю­щие элементы должны находиться в нулевом состоянии. На выходе схемы будет 0 до тех пор, пока первый элемент а_n мно­гочлена f₁(x) не достигнет конца регистра, т. е. в течение пер­вых k сдвигов. После этого на выходе в соответствии с (1.3) по­явится первый элемент частного, а именно a_n/b_k или a_n*b_k^-1, по­лучаемый умножением элемента а_n, следующего из последней ячейки памяти, на величину b_k^-1. Как видно из (1.3), для каж­дого ненулевого коэффициента частного с, из делимого необхо­димо вычесть многочлен c_if₂(x). Вычитание осуществляется в сумматорах по модулю два после умножения коэффициента частного, например a_nb_k^-1 , на множители —b_о, b₁,…,b_k-1.

Поскольку мы рассматриваем двоичное поле, то коэффици­енты b₀,b₁,…,b_k-1 могут принимать значения 0 или 1, а зна­чение b_к —только 1. Учитывая также, что при сложении по модулю 2 знак минус может быть заменен плюсом, схема на рис. 1.4 значительно упростится, если устройства умножения заменить, как и в регистрах умножения, короткими замыкания­ми для b_i = 1 и обрывом цепи для b_i = 0. При этом число встроенных в регистр сумматоров уменьшится и будет равно числу единичных коэффициентов b_i= 1 (i =0, 1, .,., k—1).

Пример. Пусть f₂ (х) = 1 +x² + х⁴ + х⁵ т. е. b_о =1, b₁=0,b₂=1,b₃=0,b₄=1,b₅=1.

Рис. 1.5. Схема деления на многочлен f(x)= 1 +x²+ х⁴+x⁵

Рис. 1.6. Схема, реализующая одновременное умножение на много член f₂(x)=b₀+b₁x+…+b_kx^k и деление на многочлен f₃(x)=c₀+c₁x+…+c_k

_bв0 -I- п.х + ... + e_kx^k и деление на многочлен /s(*) =

На рис. 1.5 представлена схема деления на заданный мно­гочлен.

На основе регистра с встроенными сумматорами может быть построена схема (рис. 1.6), реализующая одновременное умно­жение на многочлен f₂(x)=b₀+b₁x+b₂x²+…+b_kx^k и деление на многочлен f₃(x)=c₀+c₁x+c₂x²+…+c_kx^k.

2. ОБЩИЕ ПРИНЦИПЫ ПОСТРОЕНИЯ ЦИКЛИЧЕСКИХ КОДОВ

Характерной особенностью циклических кодов является представление кодовых комбинаций длины п многочленами сте­пени п— 1 вида

f(x)=c₀+c₁x+c₂x²+…+c_n-1x^n-1. (2.1)

Вследствие этого циклические коды называют часто полино­миальными кодами. Такое представление циклических кодов позволяет распространить на них приведенные выше свойства полей Галуа.

Другой распространенной формой представления комбина­ций циклического кода является векторная форма (c_oc₁c₂ ... с_n-1), где элементы кода с₁- являются коэффициентами много­члена f(x), принадлежащими простому полю GF (р). Для дво­ичных циклических кодов коэффициенты с_i принадлежат полю GF (2), т. е. принимают значения 0 и 1.

Таким образом, обе формы представления комбинаций свя­заны между собой тем, что одна вытекает из другой. Например, комбинации (1010001) соответствует многочлен f (x)= 1+x²+ х⁶.

Приведем основные свойства циклических кодов, которые определяют их построение.

Свойство 2.1. Циклический код в полиномиальном его пред­ставлении можно определить как множество многочленов степени п—1 и меньше, каждый из которых делится без остатка на некоторый многочлен Р (х), называемый образующим или порождающим многочленом кода.

Из этого свойства вытекает, что для каждой комбинации циклического кода, представленной многочленом f(x), справед­ливо сравнение

f(x)=[mod Р(х)]. (2.2)

Свойство 2.2. Если некоторая комбинация (c₀c₁c₂…c_n-1) принадлежит какому-либо циклическому коду, то и комбинация, полученная из предыдущей в результате циклического сдвига ее элементов, например (с_n-1 c₀c₁ … c_n-2), также принадлежит этому циклическому коду.

Это свойство основывается на свойстве 1.3 полей Галуа, со­гласно которому любой неприводимый в поле двоичных чисел многочлен Р (х) степени т является делителем двулена (x^{2^m-1}-1), т. е.

x^{2^m-1}-1≡0[modP(x)]. (2.3)

Таким образом, выбрав длину комбинации п, удовлетворяю­щую равенству п = 2^т — 1, получим

xⁿ-1≡0[modP(x)]. (2.4)

При таком значении п, умножив на х многочлен комбинации циклического кода f(х), представленного в виде (2.1), получим: x*f(x) =с_ох + с_]х²+ ... + с_n-2х^n-1 + с_n-1хⁿ. В силу (2.4) можно записать: с_n-1xⁿ≡с_n-1[mod Р (х)]. Тогда

x*f(x)≡с_п-1 + с_ох+с₁х² + ... +с_n-2х^п-1 (2.5)

Но так как согласно свойству 2.1 многочлен f (x) делится на Р (х) без остатка, то и многочлен xf (x), представленный много­членом (2.5), также делится на Р(х). Отсюда вектор (с_n-1с_ос₁ ... с_n-2 ), полученный из исходной комбинации цикли­ческого кода (c₀c₁c₂…с_n-1) путем циклического сдвига, будет принадлежать также циклическому коду. Из доказательства свойства 2.2 вытекает следствие, которое заключается в том. что для большинства циклических кодов п = 2^т—1, где т — степень образующего неприводимого многочлена Р (х). Но на практике иногда выбирают длину комбинации n₁меньше 2^m-1. Такой циклический код называют укороченным.

Рассмотрим теперь общие принципы построения цикличе­ского кода. Задачей кодирующего устройства является преоб­разование k-элементной комбинации (a_oa₁ ... а_k-1 ) исходного безызбыточного кода в n-элементную комбинацию (c₀c₁c₂ ... c_n-1 ) избыточного циклического (п,k)-кода. Таким образом, каждая комбинация циклического кода содержит п—k избы­точных элементов.

Задачей декодера является обратное преобразование при­нятой n-элементной комбинации циклического кода в исходную k-элементную комбинацию. При этом эффективность цикличе­ского кода оценивается его способностью корректировать воз­никающие при передаче по каналу ошибки.

Существует несколько способов кодирования. Наиболее про­стой из них заключается в том, что многочлен (2.1), соответст­вующий комбинации циклического кода, получают путем умно­жения многочлена φ(х) = a_о + а₁x+ ... a_k-1 x^k-1, соответ­ствующего исходной комбинации, на образующий многочлен Р(х) степени т, т. е.

f(x) = φ(x)P(x). (2.6)

Отсюда видно, что для циклического (п, k)-кода степень образующего многочлена m = п— k, т. е. равна числу избыточных элементов комбинации.

Циклический код, построенный в соответствии с (2.6), на­зывают несистематическим, так как среди элементов комбина­ции (c₀c₁c₂ ... c_n-1) нельзя выделить информационные и избы­точные или проверочные.

Другой способ кодирования соответствует систематическому циклическому (п, k)-коду. Построение систематического цикли­ческого кода сводится к тому, чтобы к информационным эле­ментам a₀, a₁, … a_k-1 исходного k-элементного кода добавить (п—k) полученных определенным образом избыточных элемен­тов. Причем в каждой комбинации n-элементного циклического кода информационные и избыточные элементы будут занимать определенные позиции. Значения добавленных избыточных эле­ментов должны определяться таким образом, чтобы выполня­лось свойство 2.1 циклических кодов, т. е. деление без остатка на образующий многочлен Р (х).

Чтобы построить систематический циклический код, комби­нацию исходного k-элементного кода, принадлежащую группе порядка 2^к, записывают в виде многочлена φ(х) степени к—1. Затем многочлен φ(х) умножается на х^n-k, что равносильно приписыванию к исходной k-элементной комбинации n — k ну­лей со стороны младшего разряда.

Например, необходимо умножить многочлен φ(х) = 1 +x+x² на х^n-k = х³. Тогда имеем х^n-kφ(х) = х³ + х⁴ + х⁵. Если записать многочлен φ(х) и результат умножения в виде двоичных комбинаций, то получим

Для φ(х) — 111,

для x³ φ(х) —000111.

Полученное таким образом произведение х^n-kφ(х) делим на производящий многочлен Р (х) степени n — k. При делении на производящий многочлен Р (х) образуется частное Q(х) той же степени, что и φ(х) и, кроме того, возможно появление ос­татка R (х), т.е.

Видоизменяя уравнение, получим

Очевидно, что многочлен (2.8) соответствует комбинации ци­клического кода, так как он удовлетворяет основному требова­нию циклических кодов, а именно, делится без остатка на про­изводящий многочлен Р(х).

В дальнейшем будем рассматривать только двоичные коды, поэтому знаки «+» и «—» равноценны.

Если многочлен х^n-kφ(х)+R(х) записать в виде комбина­ции, то легко заметить, что систематический циклический (n₁k)- код можно построить, приписав к каждой кодовой комбинации исходного k-элементного кода остаток от деления многочлена х^n-kφ(х) на производящий многочлен Р(х).

Рассмотрим пример построения систематического циклического (n, k)-кода, для которого n=15, k=11 и n-k=4.

В качестве производящего выбран многочлен P(x)=1+x+x⁴.

Для кодирования комбинации 10100100001, которой соответствует многочлен φ(х)=1+x²+x⁵+x¹⁰, разделим x⁴φ(х) на производящий многочлен Р(х) и найдем остаток R(х). В результате находим, что R(х)=1+x. Кодовый многочлен образуется путем сложения x⁴φ(х) и R(х) согласно (2.8):

Этому многочлену соответствует комбинация циклического кода

1100 10100100001

проверочные информационные

элементы элементы

Матричное представление циклических кодов

Систематический циклический код может быть полностью определен своей производящей матрицей, которая строится по следующему правилу. Сначала записывается единичная матрица Е_k для исходного k-элементного кода. Далее одночлен, соответствующей каждой из строк Е_k, умножается на х^n-k и делится на производящий многочлен Р(х). В результате деления получим остатки, каждый из которых соответствует определенной строке матрицы Е_k. Из этих остатков составляется дополнительная матрица R, которая приписывается к матрице Е_k. Таким образом, производящая матрица для циклического (n, k)-кода будет иметь вид G=[RЕ_k], где R-приписанная к Е_k проверочная матрица размерности k * (n-k).

Все остальные комбинации циклического кода получаются путем сложения по модулю 2 строк матрицы G в различных сочетаниях.

П ример. Пусть необходимо построить циклический код, для которого n=7, k=4, n-k=3, а P(x)=1+x+x³. Прежде всего запишем единичную матрицу Е_k:

строкам которой соответствуют одночлены 1, х, х², х³.

Каждая строка умножается на х^n-k = х³ тогда получим новую матрицу, в которой каждая строка будет сдвинута на n— k нулей.

Каждый из полученных многочленов делится на производящий многочлен Р(х) и находится соответствующий остаток степени n-k, который и записывается на месте первых нулей в новой матрице.

Найденные остатки многочленов x³, x⁴, x⁵, x⁶ на P(x)=1+x+x³ будут соответственно равны R₁(x)=1+x; R₂(x)=x+x²; R₃(x)=1+x+x²; R₄(x)=1+x².

Теперь составляем проверочную матрицу R, элементами которой являются остатки в двоичной форме записи:

Приписывая эту матрицу к единичной матриц Е_k, получим производящую матрицу для циклического кода

Образующая матрица G позволяет преобразовывать комбинацию исходного кода (a₀, a₁, … a_k-1) в комбинацию циклического кода путем ее умножения на матрицу G. Пусть для рассматриваемого примера кода исходная комбинация равна (1110), т.е. φ(х)=1+x+x². Умножив ее на матрицу G, т.е. [1110]* G, получим циклическую комбинацию (0101110).

В [7] доказана следующая теорема:

Если V-пространство строк матрицы G=[RЕ_k], где Е_k-единичная матрица размерности k*k, а R-матрица размерности k*(n-k), то V-является нулевым пространством матрицы H=[E_n-kR^T], где E_n-k- единичная матрица размерности (n-k)*(n-k), а R^T-транспорированная матрица R.

По этой теореме двоичный систематический циклический (n,k)-код, производящая матрица которого имеет вид G=[R Е_k], является нулевым пространством проверочной матрицы H=[E_{n- k}R^T] и, следовательно, G*H^T=0.

Так, для нашего примера матрица H с учетом найденного ранее матрицы R будет иметь вид:

Легко проверить, что G*H^T=0.

Для несистематического кода образующая матрица G строится в соответствии с правилом построения кода, а именно, путем умножения многочлена исходной комбинации φ(x) на порождающий многочлен Р(x). Для получения матрицы G составляют единичную матрицу E_k и каждую ее строку, представленную одночленом x_i , умножают на многочлен Р(x). Из коэффициентов полученных многочленов x_i* Р(x) составляют образующую матрицу G несистематического кода. Для рассматриваемого выше примера кода (7,4) с Р(x)=1+x+x³, записав произведения x_i* Р(x), где i=0,1,2,3, получим следующую матрицу G:

Также, как и для систематического кода, несистематический циклический код должен представлять собой нулевое пространство по отношению к некоторой проверочной матрице H, которая может быть построена по проверочному полиному

Выражение (2.9) следует из свойства 2.2 циклических кодов и сравнения (2.4), согласно которому многочлен Р (х) является делителем двучлена хⁿ + 1, где п = 2^n-k — 1. Тогда строки проверочной матрицы Н будут состоять из коэффициентов мно­гочленов хⁱН(х), где i = 0,1, ..., (п — k—1). Так, для рассматриваемого примера кода (7, 4) имеем Н(х)= =(x⁷+1)/P(x)=1+x+x²+x⁴.

Записав многочлены Н(х), xH(x), x²H(x), составим проверочную матрицу H:

в которой строки записаны начиная со старшей степени.

Легко проверить, что G*H^T =0.

Следует отметить, что может быть построена проверочная матрица H, единая как для систематического, так и для неси­стематического кода, исходя из свойства 2.1 циклических ко­дов. Из этого свойства следует, что, если некоторый элемент а поля GF(2ⁿ) является корнем многочлена Р (х), то он явля­ется также и корнем многочлена f (х). Отсюда любая комбина­ция циклического кода, представленная многочленом (2.1), удовлетворяет равенству

f(α)≡0, (2.10)

которое может быть получено как произведение [с_ос₁c₂ ... c_п-1]Н^Т, где H-проверочная матрица вида:

H=[1αα²….α^n-1]. (2.11)

Учитывая, что для рассматриваемого примера кода (7, 4) по­рождающий многочлен Р(х) = 1+х+x³ является примитив­ным и а — его корень, матрица Н будет состоять из ненулевых элементов поля GF (2³), т. е.

H=[1αα²α³α⁴α⁵α⁶].

Заменив элементы αⁱ их двоичными векторами и записав их в виде столбцов получим следующую проверочную матрицу:

Легко проверить, что полученная проверочная матрица Н удовлетворяет равенству G*H^T=0 как для систематического, так и для несистематического циклических кодов (7,4), построенных по многочлену Р(х)=1+х+х³.

Принципы обнаружения и исправления ошибок циклическими кодами

Один из принципов обнаружения ошибок основывается на делении принятой кодовой комбинации на производящий многочлен Р(х).

В общем виде принятая комбинация h(x) в полиномиальном представлении равна сумме h(x)=f(x)+e(x),

где f(x)-многочлен, соответствующий переданной кодовой комбинации,

e(x)-многочлен, соответствующий вектору ошибок.

Ошибки обнаруживаются, если остаток от деления h(x) на Р(х) не равен нулю. Если же остаток равен нулю, то ошибка или отсутствует, или не обнаруживается кодом.

Исправление ошибок является гораздо более трудной задачей, чем обнаружение. Реализация такой операции возможна,

если каждый многочлен исправляемых ошибок будет давать отличный от других ненулевой остаток после деления на Р (х). Поэтому исправление ошибки на приеме может быть осущест­влено с помощью следующих операций:

1. Принятое сообщение делится на Р(х) и вычисляется ос­таток.

2. Из таблиц пли путем некоторых вычислений находится многочлен ошибок е (х), соответствующий остатку.

3. Найденный многочлен е (х) вычитается из h (х), в ре­зультате получается f (x), т. е. переданное сообщение.

Другая, применяемая на практике процедура обнаружения и исправления ошибок циклическими кодами, основывается на том, что комбинации циклического кода являются нулевым про­странством по отношению к его проверочной матрице Н. Из этого свойства следует, что произведение вектора любой ком­бинации, принадлежащей циклическому коду, на матрицу Н^т равно нулю. Если же в принятой комбинации содержатся ошиб­ки и эта комбинация попадает в число запрещенных, то резуль­тат умножения, называемый синдромом, не будет равен нулю. Обозначив синдром через S = (s₀, s₁ ...s_n-k-1) будем иметь

(h_0,h₂,h₁…h_n-1)*H^T=(s₀s₁…s_n-k-1), (2.12)

где вектор (h₀h₁h₂…h_n-1) соответствует многочлену принятой комбинации h(x), равному h (х) = f (x) -f e (х). Таким обра­зом, ошибки обнаруживаются, если синдром S не равен нулю.

Исправить можно только те конфигурации ошибок в комби­нации, которые дают различные ненулевые синдромы.

В дальнейшем операции обнаружения и исправления оши­бок циклическими кодами будут рассмотрены на конкретных примерах.

3. ЦИКЛИЧЕСКИЕ КОДЫ, ИСПРАВЛЯЮЩИЕ ОДНОКРАТНЫЕ ОШИБКИ

Устройство, позволяющее преобразовать комбинации исход­ного k-элементного кода в комбинации циклического кода, на­зывают кодирующим.

Согласно описанному ранее принципу построения система­тического циклического (п,k)-кода, каждый многочлен φ (х), соответствующий определенной комбинации исходного кода, должен быть умножен на одночлен х^n-k затем х^п-кφ(х) делит­ся на производящий многочлен Р (х). Обе эти операции реали­зуются с помощью регистра, включенного по виду многочлена Р(х). В результате деления многочлена х^п-kφ (х) на произво­дящий многочлен Р (х) в регистре сдвига будет получен оста­ток R (х) степени, меньшей степени многочлена Р (х). Как было показано, комбинация циклического кода будет выражена в виде многочлена φ(х) с дописанным к нему остатком R (х).

Рассмотрим пример построения и принцип работы кодирую­щего устройства кода (15.11) для производящего многочлена Р(х) = 1 + х +x⁴ (рис. 3.1). Элементы комбинации, соответст­вующей многочлену φ(х), поступают на выходной сумматор, что реализует умножение х^n-kφ (х) = х⁴φ (х).

Pиc. 3.1. Кодирующее устройство системати­ческого кода (15, 11) с образующим много­членом р(х) = 1 + x+x⁴

В течение k тактов, пока на вход поступают информацион­ные элементы, ключ Кл. находится в положении 1, при этом информационные элементы без всякой задержки поступают на выход кодирующего устройства. С приходом последнего инфор­мационного элемента в регистре сдвига определяется остаток от деления х^n-kφ (х) на Р (х), после чего ключ Кл. переклю­чается в положение 2 и на выход вслед за информационными элементами считывается остаток R(x), т. е. проверочные элемен­ты. Таким образом, с выхода кодирующего устройства поступа­ет комбинация циклического кода.

Кодирующее устройство несистематического (п,k)-кода реа­лизует умножение φ(х)Р(х). Схема построения КУ для кода (15, 11) с образующим полиномом Р (х) = 1 + х + x⁴ представ­лена на рис. 3.2.

Рис. 3.2. Кодирующее устройство несистематическо­го циклического (15, 11)-кода с образующим мно­гочленом р (х)= 1 + х + х⁴

Выше было показано, что в основе декодирования лежит признак делимости принятой последовательности на производя­щий многочлен Р (х). Для обнаружения ошибок достаточно убедиться, что остаток от деления не равен нулю, Отсюда ясно, что для построения декодирующего устройства циклического кода, позволяющего только обнаруживать ошибки, можно ис­пользовать регистр сдвига с обратными связями, который реа­лизует деление на производящий многочлен Р (х).

Любой систематический (п,k)-код, исправляющий однократ­ные ошибки, должен иметь такое число п — k проверочных раз­рядов в комбинации, чтобы удовлетворялось неравенство 2^n-k≥n+1 . Код, построенный таким образом, обеспечивает мини­мальное кодовое расстояние между любыми разрешенными ком­бинациями, равное трем.

Как было показано, любая одиночная ошибка может обна­руживаться по ненулевому остатку от деления многочлена h(x), соответствующего принятой комбинации, на производящий мно­гочлен Р (х). Однако для исправления однократных ошибок требуется, чтобы любой ошибке соответствовал определенный отличный от нуля остаток и, во-вторых, чтобы все эти остатки были различны между собой, т. е., чтобы выполнялось взаимо­однозначное соответствие между местоположением ошибки и ее остатком. Эти требования выполняются, если остатки в случае одиночных ошибок будут представлять собой степени первооб­разного элемента, являющегося корнем примитивного много­члена Р(х), и, следовательно, будут ненулевыми элементами поля Галуа GF(2ⁿ). Таких различных ненулевых элементов поля GF(2^т) будет 2^m—1. Пусть на i-й позиции комбинации длины n = 2^т—I произошла ошибка, которой соответствует одночлен е (х) = хⁱ. В результате деления принятой комбина­ции на производящий многочлен Р(х) образуется остаток R(x), представляющий собой элемент а¹ поля GF(2^m), где а — перво­образный элемент поля и корень многочлена Р (х). Этот оста­ток будет содержаться в регистре сдвига, который реализует операцию деления на многочлен Р (х). При этом сдвиг содер­жимого регистра на один шаг соответствует умножению на х с последующим приведением результата по модулю Р (х). Следо­вательно, произведя (п — i) сдвигов остатка R (х), мы тем са­мым как бы умножили принятую комбинацию h (х) на х^n-1 и разделили результат на Р (х). В регистре при этом останется некоторый новый остаток R_i (х) = x^n-iR (x) [modP(x)]. Со­стояние регистра определим из преобразования:

х^п-ih(х)=х^n-i[ f(x)+ е(х)]=x^n-if(х)+х^п-iе(х)≡хⁿ ≡1[modP(x)],

где f(х) — разрешенная кодовая комбинация, выраженная в виде многочлена, делящегося на Р (х) без остатка. Следова­тельно, состояние регистра после (n — i) сдвигов будет соот­ветствовать элементу поля а°= 1. Обнаружив это состояние, можно легко исправить одиночную ошибку.

Рассмотрим процесс исправления одиночных ошибок деко­дирующим устройством (рис. 3.3) циклического (15,11)кода, производящий многочлен которого имеет вид Р (х)=1+ х+x⁴ Комбинация циклического кода поступает на вход буферного накопителя емкостью п=15 и одновременно с этим на вход регистра сдвига с обратными связями. Когда элементы комби­нации циклического кода заполнят буфер, в регистре сдвига с обратными связями будет содержаться остаток от деления при­нятой комбинации на производящий многочлен Р (х).

Рис. 3.3. Декодирующее устройство циклического кода (15, 11), исправляющего однократные ошибки

Как было показано, определение ошибочной i-й позиции для рассматриваемого кода осуществляется путем обнаружения со­стояния (1000) через (п—i) сдвигов, т. е. тогда, когда ошибоч­ный элемент уже покинет буфер. Следовательно, после буфер­ного накопителя необходимо поставить задержку на один эле­мент, что позволит исправить эту ошибку со следующим так­том (сдвигом). Чтобы предотвратить ложную работу декоди­рующего устройства во время заполнения комбинацией буфера, а также при наличии в принятой комбинации одиночной ошиб­ки на нулевой позиции, соответствующей коэффициенту при х°, поставлен ключ Кл. Этот ключ замыкается в момент поступле­ния на выходной сумматор 111 первого информационного эле­мента, соответствующего коэффициенту при х¹⁴в принятой ком­бинации, а размыкается в момент сброса регистра сдвига с обратными связями, т. е. в момент установления состояния 0000. Сброс можно осуществить, например, из блока обнаружения в момент исправления ошибки подачей единицы в сумматор 11.

Недостатком подобных схем декодирования является то, что после заполнения буферного накопителя в течение следующих п тактов информация на вход декодирующего устройства не должна поступать. В некоторых случаях в зависимости от тре­бований к системе передачи данных это время простоя можно сократить до k сдвигов, если производить исправление одиночных ошибок только среди k информационных элементов приня­той комбинации.