Прокис Дж. Цифровая связь (2000) (1151856), страница 76
Текст из файла (страница 76)
Следовательно, кодовые слова, связанные с этими полиномами, формируют базис размерности я для циклического кода (и, а) . Пример 8.1.5. Четыре строки порождающей матрицы для циклического кода (7, 4) с порождающим полиномом д(Р) = Р'+ р'+1 можно получить из полиномов Рд(Р) = Р'" + Р'"' + Р', 1 = 3, 2, 1, 0. Легко видеть, что порождающая матрица равна 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 О 1 0 (8.1.34) О 0 0 1 1 0 1 Аналогично, порождающая матрица для циклического кода (7, 4), образуемая порождающим полиномом д,(Р) = Р'+Р+1, равна 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 О (8.1.35) 0 О 0 1 0 1 1 Проверочные матрицы, соответствующие С, и С„можно сконструировать аналогичным образом, используя соответствующие обратные полиномы (задача 8,8), Заметим, что порождающие матрицы, полученные таким конструированием, не имеют систематическую форму.
Мы можем сконструировать порождающую матрицу циклического кода в систематической форме С=~1„:Р~ от порождающего полинома следующим образом. Для начала заметим, что 1-ая строка С соответствует полиному формы Р" '+Я(Р), 1=1,2, ...,1, где Л,(Р) — полипом степени, меньшей чем и — Й Эту форму можно получить делением р" ' на 8(Р) . Таким образом, имеем Р Р Р 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 О 1 1 1 1 1 Р Р 0 0 0 1 1 0 1 1 0 1 0 0 1 1 1 0 Р Р Р 0 0 0 0 0 1 1 1 1 1 1 О 1 0 0 1 1 1 0 0 1 О 1 1 0 О 1 0 0 1 0 1 1 — = 0,(р)+ — ' а(р) ' аЫ ' или, что эквивалентно р" ' =Я,(р)Др)+Р(р), 1=1, 2, ..., 7г, (8.1.3б) где Я(р) — частное. Но р" '+Я,(р) представляет кодовое слово в циклическом коде, поскольку р" '+ Л,(р) = Я(р)8(р).
Следовательно, желательный полипом, соответствующий 1-й строке С, равен р" '+Я,(р). Пример 8,1,6. Для циклического кода (7, 4) с порождающим полиномом д,(р) = р' + р+1„ранее рассмотренного в примере 8.1,5, имеем р =(р +р+1)8 (р)+р +1 р' =(р'+1)а,(р) -р'- р+1, р' = т,(р)+р'+р, р =8 (р)+р+1. Следовательно, порождающая матрица кода в систематической форме 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 0 (8.1.37) 0 0 0 1 0 1 1 и соответствующая проверочная матрица 1 1 1 0 1 0 0 (8.1.38) 0 1 1 1 0 1 0 1 1 0 1 О 0 1 или р' "Х(р) = а(р)8(р)+ (р), (8.1.39) Оставляем в качестве упражнения для читателя показать, что порождающая матрица С,, даваемая (8.1.35) и матрица С, в систематической форме (8.1.37) генерируют одинаковые наборы кодовых слов (задача 8.2). Метод конструирования порождающей матрицы С в сисгематической форме согласно (8.1.36) также подразумевает„что систематический код можно генерировать непосредственно нз порождающего полинома 8(р).
Предположим, что мы умножим полипом сообщения Х(р) на р" '. Тогда получим Х(р) — х„,р +х,,р +„.+хр +х0р В систематическом коде этот полипом представляет первые Ф бит слова С(р). К этому полиному мы должны прибавить полипом степени меньшей, чем п — 1г, представляющей проверочные символы. Теперь, если р" ~Х(р) разделить на 8(р) „результат равен Пример 8.1,7. Дуальный код для циклического кода (7, 4), порождаемого полиномом д,(р) = р' + р' +1, — это код (7, 3), который порождается обратным полиномом р'Ь,(р ')= р'+р'+р+1. Однако, мы можем также использовать Ь,(р) для получения порождающей матрицы для дуального кода.
Матрица, соответствующая полиному р'Ь,(р), ! = 2, 1, О, равна 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 1 Порождающая матрица для дуального кода (7,3), которая является проверочной матрицей для циклического кода (7, 4), состоит из строк С«„взятых в инверсном порядке. 0 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 0 Таким образом, Н, = Читатель может убедиться, что С,Н~=О. 366 где г(р) имеет степень меньшую, чем и — Ь. Ясно, что Я(р)д(р) — это кодовое слово циклического кода. Следовательно, суммируя (по то«! 2) г(р) с обеими частями (8.1.39), мы получаем желаемый систематический код. Подытоживая, скажем, что систематический код можно генерировать так: 1.
Умножаем полинам сообщения Х(р) на р" "; 2. Делим р" «Х(р) на д(р), чтобы получить остаток г(р); и 3. Добавляем г(р) к р" "Х(р). Ниже мы продемонстрируем, как эти вычисления можно выполнить, используя сдвиговые регистры с обратной связью. Поскольку р" +1= д(р)Ь(р) или, что эквивалентно, д(р)Ь(р)=0 п«ой(р" +1), мы видим, что полиномы у(р) и Ь(р) ортогоиальньь Далее, полиномы р'д(р) и р'Ь(р) также ортогональны для всех 1 и у. Однако, векторы, соответствующие полиномам д(р) и Ь( р), ортогональны только, если порядок следования элементов одного из этих векторов реверсировать. То же утверждение применимо к векторам, соответствующим полиномам р'д(р) и р'Ь(р).
Действительно, если проверочный полипом Ь(р) используется как порождающий для (и, и — ««) дуального кода, ансамбль кодовых слов, полученный так, включают в себя те же кодовые слова, которые генерируются обратным полиномом, за исключением того, что кодовые векторы реверсированы. Эго подразумевает, что порождающая матрица для дуального кода, полученная от обратного полинома р"Ь(р '), может быть также получить непосредственно от Ь(р).
Поскольку проверочная матрица Н для циклического кода (и, Й) является порождающей матрицей для дуального кода, следует, что Н также можно получить от Ь(р). Следующий пример иллюстрируют это соотношение, Замет»1м, что векторы Н, состоит из всех семи двоичных вектор-столбцов длины З„ исключая вектор из одних нулей. Но это как раз описание проверочной матрицы для кода Хемминга (7,4). Следовательно, циклический код (7,4) эквивалентен коду Хемминга (7, 4), рассмотренному ранее в примерах 8.1.1 и 8.1.2. Кодеры для циклических кодов.
Операции кодирования при создании циклических кодов можно выполнить при помощи линейных сдвигающих регистров с обратной связью, с использованием порождающего или проверочного полинома. Сначала рассмотрим использование фр). Как указано выше, генерирование систематического циклического кода включает три ступени, а именнш умножение полинома сообщения Х(р) на р" », деление этого произведения на д(Р) и в заключение, прибавление остатка г(Р) к р" »Х(Р).
Из этих трех ступеней только деление является нетривиальным. Деление полинома А(Р) = р" "Х(р) степени и-1 на полипом 8(Р) К Р +8.-»- Р + +Й~Р+8« можно выполнить посредствам (и — д) ячеек регистра сдвига с обратной связью, показанного на рис. 8.1.2. Чаатног Рис, 3» 2. Регистр сдвига с обратной связъ»о для деления лолиномв А(р) на я(р) Первоначально ячейки сдвига регистра содержит одни нули, Коэффициенты А(р) поступают и продвигаются по регистру сдвига по одному коэффициенту за такт, начиная с коэффициентов более высокого порядка, т.е. с а„,, затем а„, и так далее.
После (и — lс — 1) -го сдвига, первый ненулевой выход частного равен»7, = (д„») 'и„, . Последующие выходы генерируются так, как показано на рис. 8.1.2. Для образования каждого выходного коэффициента линии мы должны вычесть полипом 8(р), умноженный на этот коэффициент, как при обычном «длинном» делении. Это вычитание производится посредством обратной связи. Таким образом, регистр сдвига на рис. 8.1.2 обеспечивает деление двух полнномов.
В нашем случае я„» =я, =1, и для двоичных кодов арифметические операции выполняются по шо»1 2. Следовательно, операция вычитания сводится к сложению по шод 2. Далее мы будем только интересоваться генерированием проверочных символов для каждого кодового слова, поскольку код систематический. Как следствие, кодер циклического кода принимает вид, показанный на рис. 8.1.3. Збт Бипо оообмоиия Рис.
8.1.3, Циклический кодер с использованием порождающего полинома80з) Первые д бит на выходе кодера просто равны 1г информационным битам. Эти )г бит одновременно поступают на регистр сдвига, поскольку ключ 1 замкнут. Заметим, что умножение полиномов р" ~ и Х(р) явно не производится. После того как все гг информационных бита попали на вход кодера (и к модулятору), положения двух ключей на рис. 8.1.3 меняются на обратные.
Начиная с этого времени„содержимое регистра сдвига просто дает и — )г проверочных символов, которые соответствуют коэффициентам полинома остатка. Эти и — 1г бита последовательно отправляются на модулятор. Пример 8.1.8. Регистр сдвига для кодирования циклическим кодом (7, 4) с порождающим полиномом 8(р) = р'+ р+ 1 показан на рис. 8.1.4. Рис. 8.1.4. Циклический кодер (7,4) с использованием порождающего полинома 80о)=р~+р+1 Предположим, что сообщением является цепочка 0110. Содержание сдвигового регистра дано таблицей: Вхо П1агс вига Соде жимое егис а 000 000 110 101 100 368 Такиьг образом, три проверочных символа: 100.
Они соответствуют кодовым символам с, = О, со = 0 и ст = 1. Вместо использования порождающего полинома 8(р), мы можем выполнить кодер циклического кода, используя проверочный полипом )г(р) = р" +)г~,р" '+...+й,р+ 1, Соответствующий кодер показан на рис. 8.1.5. Первоначально Й информационных символа (бита) передвигаются по регистру сдвига и одновременно поступает на модулятор. После того, как все Й информационных символов пройдут по регистру, ключ переводится в положение 2, и сдвиговой регистр работает еще и — 1г такта, генерируя и — 1 проверочных символов, как показано на рис.
8.1.5. Биты о о о Рис. а.1,5. Циклический кодер (л,т1) с испольюванием проверочного полинома «(р) Пример 8.1,9. Проверочный полипом для циклического кода (7,4), генерируемый порождающим полиномом 8(р) = р'+р+1, равен Ь(р) = р'+ р'+р+1. Кодер для этого кода, основанный на проверочном полиноме, иллюстрируется на рис. 8.1.б, Если на входе кодера действует сообщение 0110, то проверочными символами являются с, =О, с, = О, с, = 1, как легко проверить. Вывод оцооо1 Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
