Декодирование циклического кода доклад
Обновлено: 30.06.2024
Циклический код – это разновидность линейных блочных кодов (обладают теми же свойства ). Дополнительное свойство: комбинация, полученная после циклической перестановки символов в последовательности, взятой из кодовой таблицы, принадлежит той же таблице. Коды разрабатывались для того чтобы для кодирования и декодирования можно было использовать простые устройства.
для описания n-разрядных комбинаций s, состоящих из M-ичных символов, удобно использовать полиномы
где sj=0; 1;…; M-1.
Способы кодирования и декодирования конкретным циклическим кодом полностью определяются его производящим полиномом степени r
где , причём всегда . Формально этот полином тоже содержит n членов, просто у него при .
Фундаментальное свойство циклического кода состоит в том, что полином s(x), соответствующий любой разрешённой (передаваемой) комбинации s, делится без остатка на производящий полином
Отсюда следует метод декодирования принимаемой комбинации v(x): нужно вычислить остаток res(x) от деления этого полинома на g(x). Степень полинома res(x) не превышает r-1, то есть этот остаток содержит r бит. Если оказалось, что , то это несомненно указывает на наличие ошибок в принятой комбинации (обнаружение ошибок).
Напомним, что переданная s и принятая v комбинации связаны соотношение (3.2), откуда следует
| v(x)=s(x)+e(x), | (3.42) |
где e(x) – полином ошибок. Тогда с учётом (3.41) имеем соотношение, аналогичное формуле (3.17),
| res(x)=v(x)modg(x)=s(x)modg(x)+e(x)modg(x)=e(x)modg(x), | (3.43) |
то есть величина остатка не зависит от того, какая комбинация была передана, а зависит лишь от того, какие произошли ошибки. Требования к производящим полиномам:
где р – целое число ;
где - максимальная кратность гарантированно исправляемых ошибок, при этом кодовое расстояние . При это неравенство обычно обращается в равенство.
для любого b(x), если и . Это значит, что многочлен g(x) является неприводимым (простым), то есть не делится без остатка ни на какой другой многочлен, кроме 1 и самого себя.
то есть двучлен делится без остатка на g(x) (сравните это с формулой (3.18)).
Кодирование в несистематическом виде:
| s(x)=a(x)g(x), | (3.45) |
Для кодирования в систематической форме
Операции, определяемые этим выражением, можно детализировать следующим образом:
1) умножение a(x) на означает, что k информационных символов сдвигается на r позиций вправо и в итоге занимают k старших (по степеням x) разрядов; r разрядов слева при этом оказываются нулевыми;
2) вычисляется r-разрядный остаток res(x) от деления полинома , соответствующего полученной таким образом комбинации;
3) эти r элементов остатка помещаются на r нулевых позиций комбинации, полученной в пункте 1, в качестве проверочных символов.
для кодирования/декодирования циклическим кодом не требуется использования производящей и проверочной матриц. Но матрицы существуют и имеют следующий вид:
где - полином, согласованный с h(x), то есть коэффициенты этого полинома записаны в обратном порядке . Например, при n=7 для имеем .
Рассмотрим пример. код (7,4). производящий полином: .
Схема кодера, реализующего метод (3.45), приведена на рис. 3.3. Ячейки регистра обнуляются, затем при замкнутом ключе K в кодер вводятся 4 информационных символа, при этом в схеме вычисляются и выводятся 4 первых символа кодовой комбинации. Далее ключ K размыкается, и в течении следующих трёх тактов вычисляются и выводятся значения .
Схема кодера систематического кода, реализующая метод (3.46), дана на рис. 3.4.
Это схема деления полинома на полином g(x), но, в отличие
от схемы рис.2.11, она построена несколько иначе, поскольку ориентирована не на вычисление частного, а на вычисление остатка. Регистр обнуляется, переключатель П переводится в положение 2, и
в течение 4 тактов в кодер вводят 4 информационных символа. Одновременно эти символы поступают на выход в качестве информационной части кодовой комбинации (обратите внимание, что ввод и вывод производятся в обратном порядке, начиная с коэффициентов при старших степенях x). В это время в регистре с обратными связями начинается вычисление остатка. Затем переключатель П переводится в положение 1, отключая вход, и в течение следующих 3 тактов завершается вычисление остатка и его элементы выводятся на месте проверочных символов кодовой комбинации
Схема декодера, приведённая на рис. 3.5, также ориентирована на вычисление остатка от деления полинома v(x) на полином g(x). Регистр обнуляется, ключ K замыкается, и в течение 7 тактов в регистр вводятся 7 символов принятой комбинации, начиная с v6 (старшего разряда). После завершения ввода в ячейках регистра оказывается записанным значение остатка res(x). Если res(x)=0 (в 3 ячейках регистра оказались нули), считают, что в принятой комбинации ошибок нет, и на этом декодирование заканчивается.
В противном случае , ключ К размыкается (фактически это соответствует ситуации, когда последующие входные символы равны нулю), и подают ещё 7 тактовых импульсов, формально продолжая процесс деления. Номер такта, на котором в ячейках регистра оказывается комбинация 100 (это случай res(x)=1, учитывается обратный порядок следования символов), и есть номер ошибочного символа. После этого исправление этого символа и отделение информационных символов – это тривиальные операции.
Чтобы не было сомнений, заметим, что ожидаемая комбинация 100 в течение 7 тактов обязательно появится, причём один раз. Дело в том, что при отключении входа схема рис. 3.5 превращается в генератор двоичной псевдослучайной М-последовательности с периодом (2.21) равным 7. Свойства М-последовательности таковы, что в течение периода в ячейках генератора обязательно по одному разу оказываются записанными все r-разрядные двоичные комбинации, кроме нулевой, разумеется.
Обратите внимание, что наличие сумматоров на стыках между ячейками регистра сдвига определяется значениями коэффициентов полинома g(x): сумматор есть, если , и он отсутствует, если . Таким образом, зная g(x), можно сразу составить схемы кодера и декодера для любого циклического кода (или схему генератора М-последовательности).
Как показывает практика, формальное запоминание приведённых соотношений и схем мало что даёт для понимания сути вопроса, если детально не разобрать хотя бы десяток конкретных численных примеров. В частности, если нужно закодировать информационную последовательность 0011, для которой , то, проследив такт за тактом работу схемы рис.3.4 и записывая содержимое ячеек, можно убедиться в том, что на выходе появится комбинация 1100010, которой соответствует полином (значение этого полинома вычислите отдельно по формуле (3.46) и сравните с комбинацией).
В заключение обязательно нужно отметить следующее обстоятельство. Благодаря циклическому свойству, при кодировании и декодировании циклического кода удаётся организовать конвейерную обработку длинных последовательностей символов в устройствах, содержащих удивительно малое количество простейших логических элементов. Например, для кода (255,247) кодер и декодер содержат по 8 ячеек регистра сдвига и по 4 сумматора по модулю 2. Благодаря этому ценному качеству среди всевозможных линейных блочных кодов именно циклические коды нашли наиболее широкое применение.
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций.
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни.
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим.
Циклические коды
Циклические коды относятся к линейным кодам. Специфические свойства данного вида кодов помогают как при кодировании/декодировании, так и при аппаратной реализации этих процессов.
Одно из определений циклического кода Определение Линейный код называют циклическим, если для любого кодового слова [x n x 0 x 1 . x n-1 ] циклическая перестановка символов [x 0 x 1 . x n-1 x n ] также дает кодовое слово.
Рассмотрим операции с многочленами подробнее.
Полиномиальная арифметика
Рассмотрим многочлены с коэффициентами из поля Z 2 . Сложение, умножение и деление полиномов проводится как обычно.
Для тех, кто это подзабыл, приведем пример на деление.
Пример 1
(В арифметике поля Z 2 x + x = 0 , т.к. в более подробной записи x + x = (1 + 1)*x = 0*x = 0). Таким образом, 1 + x 2 делит 1 + x + x 2 + x 5 нацело и результат есть 1 + x + x 3 .
Напомним также модульную арифметику многочленов. Многочлены называются сравнимыми по модулю многочлена p(x), если их разность делится на p(x) нацело. Поэтому для получения f(x)(mod p(x)) вам нужно просто разделить f(x) на p(x) и взять остаток от деления. Заметим, что если степень f(x) меньше степени p(x), то результатом будет просто f(x)
Пример 2
Замечательным свойством полиномиального представления кодов является возможность осуществить циклический сдвиг на одну позицию вправо простым умножением кодового многочлена степени n-1 на многочлен "x" и нахождения остатка от деления на x n + 1.
Пример 3
Осуществить единичный правый циклический сдвиг кодового слова [1011], используя полиномиальную интерпретацию.
Вектору [1011] соответствует полином 1 + x 2 + x 3 . Умножим его на x, что дает get x + x 3 + x 4 . Далее, найдем остаток от деления на x n + 1, т.е. x + x 3 + x 4 (mod x n + 1) = x + x 3 + x 4 (mod x 4 + 1). Результат 1 + x + x 3 . Многочлен 1 + x + x 3 соответствует вектору [1101], который получается из [1011] правым циклическим сдвигом на одну позицию.
Порождающий многочлен
Tеорема
Многочлен g(x) является порождающим многочленом линейного циклического кода длины n тогда и только тогда, когда g(x) делит 1 + x n .
Пример 4
Алгоритм декодирования
- Найти синдромный многочлен s(x) = r(x)(mod g(x)), где r(x) полученное слово.
- Для каждого i >= 0, вычислять s i (x) = x i s(x)(mod g(x)) до тех пор, пока не будет найден, s j такой, что для него (вес)wt(s j ) n-j s j (x) (mod (1 + x n ))
Пример 4 (прод.)
Декодировать полученное слово [011010111010010], которое было отправлено после кодирования кодом из первой части примера 4. Соответствующий вектору [011010111010010] многочлен x + x 2 + x 4 + x 6 + x 7 + x 8 + x 10 + x 13 Найдем многочлен-синдром, (напомню, что g(x) = 1 + x 4 + x 6 + x 7 + x 8 ). x + x 2 + x 4 + x 6 + x 7 + x 8 + x 10 + x 13 (mod 1 + x 4 + x 6 + x 7 + x 8 ) = x 2 + x 6 + x 8
Для кодового слова синдром, как известно, равен 0. В данном случае это не так, посланное слово было искажено помехой. В соответствии с описанной процедурой декодирования будем вычислять s i (x) = x i (x 2 + x 6 + x 8 )(mod g(x)) для последовательных возрастающих значений i пока не найдем многочлен степени меньшей или равной двум (число ошибок t = 2 ).
s 1 = xs(x)(mod g(x)) = (x 3 + x 7 + x 9 )(mod g(x)) = x 3 + x 4 + x 5 + x 6 + x 7
s 2 = x 2 s(x)(mod g(x)) = (x 4 + x 8 + x 10 )(mod g(x)) = 1 + x + x 2 + x 5
s 3 = x 3 s(x)(mod g(x)) = (x 5 + x 9 + x 11 )(mod g(x)) = x + x 2 + x 3 + x 6
s 4 = x 4 s(x)(mod g(x)) = (x 6 + x 10 + x 12 )(mod g(x)) = x 2 + x 3 + x 4 + x 7
s 5 = x 5 s(x)(mod g(x)) = (x 7 + x 11 + x 13 )(mod g(x)) = 1 + x 3 + x 5 + x 6 + x 7
s 6 = x 6 s(x)(mod g(x)) = (x 8 + x 12 + x 14 )(mod g(x)) = x + 1
x + 1 имеет вес 2, поэтому для нахождения многочлена ошибок вычисляем e(x) = x 15-6 s 6 (x)(mod (1 + x n )) = x 9 (x + 1)(mod (1 + x n )) = x 10 + x 9 .
Итак, если отправленное кодовое слово имеет не более двух ошибок, то оно было таким
(x + x 2 + x 4 + x 6 + x 7 + x 8 + x 10 + x 13 ) + (x 10 + x 9 ) =
x + x 2 + x 4 + x 6 + x 7 + x 8 + x 9 + x 13
x + x 2 + x 4 + x 5 ,
IV. Размерность, порождающая и проверочная матрицы
Сейчас мы рассмотрим, как идеи, которые первоначально обсуждались применительно к линейным кодам, будут интерпретироваться при полиномиальном описании циклических кодов.
Теорема: Если ПМ g(x) кода C имеет степень n-k тогда C является (n,k)-циклическим кодом. Если g(x) = a 0 + a 1 x + a 2 x 2 + . + a n-k x n-k , то порождающая матрица кода C k x n матрица вида:
Док-во: Векторы g(x), xg(x), x 2 g(x), . x k-1 g(x) линейно -независимы. IВ противном случае существует нетривиальный набор коэффициентов такой, что
b 0 g(x) + b 1 xg(x) + b 2 x 2 g(x) + . + b k-1 x k-1 g(x) = 0,
(b 0 + b 1 x + b 2 x 2 + . + b k-1 x k-1 ) g(x) = 0.
Но степень этого произведения k - 1 + n - k = n - 1 n - 1), кроме как при всех b i = 0.
Пусть c(x) из C, тогда c(x) = b(x) g(x) и можно заключить, что b(x) имеет степень n - 1 и придется приводить к остатку по mod (x n - 1), b'(x), удовлетворяющему этому ограничению на степень ). Таким образом, c(x) может быть представлено линейной комбинацией функций вида x i g(x).
Система , 0 perp . Покажем, что дуальный циклическому коду C код C perp также циклический.
Рассмотрим многочлен h(x) = (x n - 1)/g(x), где g(x) ПМ кода C. Если deg(g(x)) = n - k, то deg(h(x)) = k и он также нормированный, поэтому h(x) порождает циклический код C' размерности n - k. Пусть c 1 (x) = a 1 (x)g(x) из C и c 2 (x) = a 2 (x)h(x) из C'. Тогда
c 1 (x) c 2 (x) = a 1 (x)g(x)a 2 (x)h(x) = a 1 (x)a 2 (x)f(x) = 0 (mod f(x)),
где f(x) = x n - 1. Поэтому, используя умножение многочленов по модулю mod f(x), произведение любого кодового многочлена из C и любого многочлена из C' будет давать 0. Означает ли это, что C' -- дуальный к C код? К сожалению нет, поскольку построенный изоморфизм не сохраняет скалярное произведение, т.е. скалярное произведение векторов не соответствует нулевому произведению многочленов. Однако, коды C' и C тесно связаны - они эквивалентны.
Рассмотрим два вектора:
a = (a 0 a 1 . a n-1 ) из C
и
b = (b 0 b 1 . b n-1 ) из C',
и их произведение (вернее, соответствующих многочленов)
для каких-то c i из F. Свободный член произведения
c 0 = a 0 b 0 + a 1 b n-1 + a 2 b n-2 + . + a n-1 b 1 ,
т.к x n = 1 (mod f(x)). Теперь c 0 можно записать как скалярное произведение
где b' вектор, полученный из b циклическим сдвигом координат b на одну позицию влево и изменением порядка записи координат (т.е. (b 0 b n-1 b n-2 . b 1 )). Заметим, что умножение многочлена [sum from to c i x i ] на x n-t приводит к тому, что c t становится свободным членом, а значит c t -- свободный член a(x)(x n-t b(x)). Поэтому,
где b' теперь вектор, связанный с x n-t b(x). По отношению к b(x), b' это вектор, полученный циклическим сдвигом b на t+1 позиций влево с последующим изменением порядка координат на противоположный.
Примет: Пусть n = 3, и вектора a = (a 0 a 1 a 2 ) и b = (b 0 b 1 b 2 ). Перемножая их по mod x 3 - 1, получим
a(x)b(x) = (a 0 + a 1 x + a 2 x 2 )(b 0 + b 1 x + b 2 x 2 )
= (a 0 b 0 + a 1 b 2 + a 2 b 1 ) + (a 0 b 1 + a 1 b 0 + a 2 b 2 )x + (a 0 b 2 + a 1 b 1 + a 2 b 0 )x 2 .
Коэффициент при x 2 будет a (b 2 b 1 b 0 ). Этот вектор b' получен из b сдвигом на 3 ( = 2 + 1) позиции влево (это ставит все координаты на старые места) и изменением порядка координат с последней на первую. b-вектор в коэффициенте при x получается из b сдвигом на 2 ( = 1 + 1) позиции влево, что дает (b 2 b 0 b 1 ) и изменением порядка следования (b 1 b 0 b 2 ).
Теперь поскольку a(x)b(x) = 0 mod (x n - 1), коэффициенты при всех степенях x должны равняться 0. Вышеприведенное рассуждение приводит к заключению, что ac = 0 (т.е., векторы a и c ортогональны) для c полученного любой циклической перестановкой (сдвигом) вектора, координаты которого имеют противоположный порядок следования, чем у b . Поскольку h(x) порождает код C', это базис для C' и G' = [h(x), xh(x), . x n-k-1 h(x)] t -- порождающая матрица для C'. Теперь G' порождает код C' той же размерности n - k, что и C . Более того, взяв в качестве b(x) сам h(x), мы видим, что обратнопереставленный любой вектор из C' ортогонален любому вектору из C. Это означает, что переставив в обратном порядке колонки G', мы получим матрицу H, которая порождает код C perp , а значит является проверочной для C.
Пример: Предположим, что мы хотим построить порождающую матрицу для (7,4)- бинарного циклического кода. Поскольку g(x) = 1 + x + x 3 делит f(x) = x 7 - 1, то g(x) порождает (7,4) - циклический код C. h(x) = f(x)/g(x) = 1 + x + x 2 + x 4 порождает (7,3)-циклический код C'. Порождающая матрица для C
Порождающая матрица для C'
Перепишем колонки G' в обратном порядке, получим порождающую матрицу для C perp (она же проверочная для исходного кода)
Нетрудно проверить, что GH T = 0.
Поскольку C' и C perp могут быть получены простой перестановкой координат всех векторов - это эквивалентные коды. Повторим ранее данное определение,
Заметим, что h R (x) = x k h(1/x), где k = deg h(x). Суммируя все вышесказанное, получим следующее.
Tеорема : Пусть g(x) -- нормированный делитель f(x) = x n - 1 степени n-k, и, следовательно, ПМ для циклического (n,k)-кода C. Пусть h(x) = f(x)/g(x). Тогда h R (x) -- обратный многочлен к h(x), есть ПМ кода C perp .
V. Синдромы и охота на ошибки
Прежде всего рассмотрим альтернативный вид [R, I k ] порождающей матрицы циклического кода (систематический). Пусть g(x) ПМ кода. Разделим x n-k+i на g(x) для 0 n-k+i = q i (x)g(x) + r i (x)
где deg(r i (x)) i (x) = 0. Then
x n-k+i - r i (x) = q i (x)g(x) in C
система k линейно независящих кодовых слов, матрица, по строкам которой записаны эти слова, есть порождающая матрица требуемого вида.
Пример : Рассмотрим бинарный (7,4)-циклический код, порожденный g(x) = 1 + x + x 3 . Алгоритм деления дает:
x 3 = (1)(x 3 + x + 1) + (1+ x)
x 4 = (x)(x 3 + x + 1) + (x + x 2 )
x 5 = (x 2 + 1)(x 3 + x + 1) + (1 + x + x 2 )
x 6 = (x 3 + x + 1)(x 3 + x + 1) + (1 + x 2 ).
Порождающая матрицаЗаметим, что строки R как раз остатки от деления.
Соответствующая проверочная матрица это H = [I n-k -R t ]. Разделение матрицы подобным образом предоставляет возможность удобной полиномиальной интерпретации синдрома вектора.
Tеорема : Пусть r(x) и s(x) есть соответствующие полиномиальные представления для вектора r и его синдрома s = H r t . Тогда s(x) -- остаток от деления r(x) на g(x).
Док-во: Пусть r(x) = a 0 + a 1 x + . + a n-1 x n-1 . Заметим, что столбцы i, 0 i a столбцы j, n-k j-n+k (x), так что
где h(x) = a n-k q 0 (x) + . + a n-1 q k-1 (x). Таким образом r(x) = h(x)g(x) + s(x). Поскольку deg r i (x) n-k-1 g'(x)) n-k-1 g(x). Приходим к выводу:
r(x) = 1 + x 2 + x 3 + x 5 + x 6 .
Если разделить r(x) на g(x), то получим
r(x) = (x 3 + x 2 + x + 1)g(x) + x 2 .
Остаток, как и следовало ожидать, равен s .
А теперь найдем остаток циклического сдвига r . Положим w = (1101101), что соответствует многочлену xr(x). H w t = (110) t . В полиномиальной интерпретации этот синдром получается так. Поскольку deg s(x) = 2 = n-k-1, синдром xr(x) есть
xs(x) - 1g(x) = x 3 - (x 3 + x + 1) = 1 + x.
Предыдущее расмотрение дает нам интересный метод декодирования некоторых видов ошибок в циклических кодах. Эту технику иногда называют охотой(капканы) на ошибки ( error trapping) .
Предположим, что C это (n,k)-код с минимальным расстоянием d = 2t + 1, и проверочной матрицей H = [I n-k A]. Пусть c кодовое слово и e вектор ошибки веса не более t. Если получено r = c + e , то синдром r равен
s = H r t = H ( c + e ) t = H e t .
Пусть e* = ( s t , 0 ), где 0 это k-вектор из 0'ей. Тогда H e* t = s , т.е. e* и e имеют один и тот же синдром, значит в одном смежном классе C. Теперь пусть wt( s ) e* ) e = e* , поскольку смежный класс содержит не более одного вектора веса меньше или равного t.
Следовательно, в этом случае ошибка известна и равна e = ( s t ,0).
- Вычислим синдром s 0 (x) of r(x) по алгоритму деления.
- Положим i = 0.
- Если wt(s i (x)) n-i (s i , 0 ), и декодируем to r(x) - e(x).
- Положим i = i + 1.
- Если i = n then stop; ошибка не исправляется.
- Если deg s i-1 (x) i (x) = xs i-1 (x); иначе s i (x) = xs i-1 (x) - g(x).
- Go to (3).
r(x) = (x 3 + 1)g(x) + (x + x 2 ),
так s(x) = x + x 2 .Так как вес s(x) > 1 (= t), вычислим синдром s 1 (x) xr(x). Так как of s(x) = 2 = n - k - 1, умножаем s(x) на x и делим на g(x), что дает s 1 (x) = 1. Поскольку вес 1, мы получили маску ошибки
e(x) = x 7-1 (s 1 , 0 ) = x 6 (1000000) = x 6 .
Так как n = 7 все ошибки веса 1 имеют циклический сдвиг на шесть 0's и 6 > k = 4, исправляются все единичные ошибки..
Пример : g(x) = 1 + x 4 + x 6 + x 7 + x 8 порождает бинарный (15,7)-циклический код. Если минимальное расстояние 5(так), то t = 2. Некоторые (по меньшей мере) веса 2 маски ошибок могут содержать сдвиги не менее 7 0й и могут бытьотловлены. Если мы получили
r = (1100 1110 1100 010)
r(x) = (x + x 2 + x 4 + x 5 )g(x) + (1 + x 2 + x 5 + x 7 ).
Вычисляем синдромы s i (x) для x i r(x) пока wt(s i (x)) e = x 15-7 (s 7 , 0 ) = x 8 (100001000000000) = (0000 0000 1000 010),
Основу кодирующих и декодирующих устройств циклических кодов составляют регистры сдвига с обратными связями, позволяющие осуществлять как умножение, так и деление многочленов с приведением коэффициентов по модулю два. Такие регистры также называют многотактными линейными переключательными схемами и линейными кодовыми фильтрами Хаффмена. Они состоят из ячеек памяти, сумматоров по модулю два и устройств умножения на коэффициенты многочленов множителя или делителя. В случае двоичных кодов для умножения на коэффициент, равный 1, требуется только наличие связи в схеме. Если коэффициент равен 0, то связь отсутствует. Сдвиг информации в регистре осуществляется импульсами, поступающими с генератора продвигающих импульсов, который на схеме, как правило, не указывается. На вход устройств поступают только коэффициенты многочленов, причем начиная с коэффициента при переменной в старшей степени.
На рис. 4.9 представлена схема, выполняющая умножение произвольного (например, информационного) многочлена
на некоторый фиксированный (например, образующий) многочлен
Произведение этих многочленов равно
Предполагаем, что первоначально ячейки памяти находятся в нулевом состоянии и что за коэффициентами множимого следует n-k нулей.
На первом такте на вход схемы поступает первый коэффициент аk-1 многочлена а(х) и на выходе появляется первый коэффициент произведения, равный
На следующем такте на выход поступит сумма
т.е. второй коэффициент произведения, и т. д. На n-м такте все ячейки, кроме последней, будут в нулевом состоянии и на выходе получим последний коэффициент а0g0
Используется также схема умножения многочленов при поступлении множимого младшим разрядом вперед (рис. 4.10).
На рис. 4.11 представлена схема, выполняющая деление произвольного многочлена, например
на некоторый фиксированный (например, образующий) многочлен
Обратные связи регистра соответствуют виду многочлена g(x). Количество включаемых в него сумматоров равно числу отличных от нуля коэффициентов g(x), уменьшенному на единицу. Это объясняется тем, что сумматор сложения коэффициентов старших разрядов многочленов делимого и делителя в регистр не включается, так как результат сложения заранее известен (он равен 0).
Деление заканчивается с приходом последнего символа многочлена-делимого. При этом разность будет иметь более низкую степень, чем делитель. Эта разность и есть остаток.
Отметим, что если в качестве многочлена-делителя выбран простой многочлен степени m = n-k, то, продолжая делить образовавшийся остаток при отключенном входе, будем получать в регистре по одному разу каждое из ненулевых m-разрядных двоичных чисел. Затем эта последовательность чисел повторяется.
Пример 37. Рассмотрим процесс деления многочлена а(х)х т =(x 3 +1)x 3 на образующий многочлен g(x) = х 3 + х 2 +1. Схема для этого случая представлена на рис. 4.12, где 1, 2, 3-ячейки регистра. Работа схемы поясняется табл. 4.16.
Вычисление остатка начинается с четвертого такта и заканчивается после седьмого такта. Последующие сдвиги приводят к образованию в регистре последовательности из семи различных ненулевых трехразрядных чисел. В дальнейшем эта последовательность чисел повторяется.
Рассмотренные выше схемы умножения и деления многочленов непосредственно в том виде, в каком они представлены на рис. 4.10, 4.11, в качестве кодирующих устройств циклических кодов на практике не применяются: первая - из-за того, что образующаяся кодовая комбинация в явном виде не содержит информационных символов, а вторая - из-за того, что между информационными и проверочными символами образуется разрыв в n - k разрядов.
Раздел: Информатика, программирование
Количество знаков с пробелами: 229704
Количество таблиц: 44
Количество изображений: 52
Читайте также: