Схемы деления на образующий многочлен

Существует два принципиально различных подхода к построению схем деления. Первый реализует последовательный метод деления и создается на базе регистров сдвига с обратными связями. Второй реализует параллельный метод деления и строится только на сумматорах по модулю два. Рассмотрим первый метод.

Схема деления на регистре сдвига с сумматорами по модулю 2.

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

Рассмотрим схему деления на основе m-разрядного регистра сдвига. Строится схема по следующему правилу:

- число ячеек регистра равно степени образующего многочлена; ячейка регистра для старшей степени многочлена отсутствует, но всегда присутствует ячейка ;

- сумматоры ставятся перед ячейками регистра, соответствующими ненулевым членам образующего многочлена, при этом сумматор, соответствующий старшему члену образующего многочлена, отбрасывается;

- делимое, начиная со старшего разряда, поступает на вход первого сумматора, соответствующего члену ;

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

Составленная в соответствии с этими правилами схема деления на образующий многочлен представлена на рис. 2.4.

Рис. 2.4. Схема деления на базе регистра сдвига.

Чтобы проследить работу схемы, составим таблицу состояний ячеек регистра.

Характерной особенностью построения регистра является то, что ячейки памяти имеют двухступенчатую структуру. Прием информации в первую ступень осуществляется по переднему фронту ТИ, а передача информации из первой ступени во вторую – по заднему фронту.

В таблице 2.5 символы 0 и 1 характеризуют состояние второй ступени ячеек памяти, устанавливающееся после прохождения заднего фронта ТИ.

Перед началом деления все ячейки регистра устанавливаются в нулевое состояние под действием импульса «Сброс».

Таблица 2.4

Таблица состояний ячеек регистра

За первые m тактов ( ) коэффициенты многочлена-делимого, подаваемые на вход схемы деления, заполняют регистр, причем коэффициент при x в старшей степени появляется на выходе ячейки . В следующем такте 1 с выхода ячейки по цепи обратной связи подается на вторые входы сумматоров по модулю 2, что равносильно вычитанию образующего многочлена из многочлена-делимого. Если после окончания предыдущего такта на выходе ячейки , соответствующей старшей степени остатка, устанавливается 0, то в следующем такте образующий многочлен не вычитается. Коэффициенты делимого просто смещаются вперед по регистру на один разряд, что находится в полном соответствии с тем, как это делается при делении многочленов столбиком. После окончания n-го такта ( ) в ячейках регистра хранятся коэффициенты остатка от деления многочлена-делимого на образующий многочлен.

Примеры решения задач

1.Используя матричное представление построить контрольную матрицу для линейного кода (11,7).

Решение: линейные коды обозначают как -коды, где – значность кодовой комбинации, а – число информационных символов в ней. Согласно заданию имеем: =11, =7. Следовательно, .

Строим порождающую матрицу:

Контрольная матрица

2.Построить контрольную матрицу линейного кода, ориентированного на исправление однократных ошибок. Требуемый объем кода Q=40.

Решение:

Определяем требуемое число информационных разрядов:

, ,

Так как код должен исправлять только одиночные ошибки, определение числа контрольных разрядов осуществляется в соответствии с выражением: . Имеем: . Следовательно, .

Строим порождающую матрицу :

Контрольная матрица

3.Из канала связи поступила комбинация линейного кода . Определить, какое число было передано. Контрольная матрица имеет вид:

Решение:

Находим синдром ошибки

Итак, синдром ошибки . Он совпадает с 1-м столбцом контрольной матрицы, следовательно, ошибка произошла в этом разряде. Исправляем этот разряд . По контрольной матрице определяем, что контрольными разрядами являются 2, 3 и 7 разряды. Следовательно, информационная часть имеет вид 0111= . Передавалось число .

4.Закодировать линейным кодом число . Контрольная матрица имеет вид:

В формируемой комбинации контрольными разрядами будут , и (соответствуют столбцам контрольной матрицы с одной 1). Составляем выражение для определения контрольных разрядов. Для того, чтобы формируемый кодовый вектор был ортогонален вектору должно выполняться равенство:

Ортогональность вектора будет достигнута, если .

Ортогональность вектора достигается, если .

В окончательном виде .

5.Закодировать циклическим кодом , образующий многочлен .

Разрешенные комбинации циклического кода формируются в соответствии с выражением: , где – многочлен, отображающий информационную часть; m – степень образующего многочлена, m=3; – остаток от деления многочлена на .

В виде кодовых векторов указанные многочлены имеют вид:

; .

Находим остаток :

Итак, в виде КВ имеет вид: .

6. Из канала связи поступила комбинация ЦК 1001100, . Определить, какое число передавалось.

Находим остаток от деления принятого КВ на :

Образующий многочлен имеет 3 ненулевых члена, следовательно, кодовое расстояние кода, порождаемое этим многочленом, и код способен исправлять только однократные ошибки, т.е. .

Имеем: вес остатка . Следовательно, принятую комбинацию нужно смещать циклически влево и вновь делить на :

Требуется еще сдвиг:

Складываем:

и сдвигаем в обратную сторону на 3 такта: . Контрольные разряды отбрасываем. Получаем: .

7.Построить схему делителя на образующий многочлен

Пример задания по контрольной работе – часть 3

1. Построить контрольную матрицу для линейного кода, ориентированного на исправление однократной ошибки. Требуемый объем кода Q=30.

2. Определить, какое число передавалось, если принятая комбинация имеет вид 0110111, а

3. Закодировать линейным кодом число 14₁₀. Контрольная матрица та же, что и в п.2.

4. Закодировать ЦК число 24₁₀, если .

5. Определить, какое число передавалось, если принятая комбинация имеет вид 1100111, а .