2. Перепишем (31), вводя положительные степени:

Сумма справа – это полином, представляющий некоторое кодовое слово (С_L-1, ..., C₁, C₀). Символы в кодовых словах располагают справа налево (от младшего к старшему разряду). В z-преобразовании (31) символы кодовых слов расположены в обратном порядке – по ходу «текущего» времени.

При переходе к схемам прежде всего обратим внимание на особенность операций с полиномами (31) в модульной арифметике.

Положим, дана последовательность из трёх элементов с = (1, 0, 1). Z-преобразование последовательности можно представить в двух вариантах:

D_c(z) = 1+ z^–2 = (1 + z^–1)∙(1 + z^–1), mod 2 . (32)

Проверить равенство несложно:

(1 + z^–1) (1 + z^–1) = 1+ (1 + 1) z^–1 + z^–2 =1 + z^–2, mod 2.

Второй вариант в (32) получен на основании теоремы о разложении многочленов на множители. Если z₁ и z₂ – корни уравнения D_c(z) = 0, то можно записать:

D_c(z) =1 + z^–2 = (1 + z²) / z² = ((z – z₁)∙(z – z₂)) / z².

В данном случае уравнение

1 + z² = 1 – z² = 0, mod 2,

имеет один корень (кратности 2): z₁ = z₂ = 1. Он и представлен в формуле (32).

Заметим, что в операции сложения по mod 2 знаки «+» и «–» тождественны, нет различия между (+1) и (–1).

На основании (32) можно составить две схемы генерации чисел с= = (1, 0, 1). С учётом условия (26) генерации редких импульсов получим схемы, приведенные на рис. 9,а,б.

а б

Рис.9

Каскадная структура рис.9,б следует из представления системной функции D_c(z) в виде произведения.

Положим теперь, что импульсная последовательность С_n состоит только из одноразрядных единиц: С_n = 1, n =0, 1, … . В этом случае z-преобразование приводит к результатам, схожим с (15) для геометрических прогрессий:

(33)

Проверить эти равенства несложно. Достаточно раскрыть произведения и объединить члены с одинаковыми степенями z:

а) (1 + z^–1 + z^–2 +…)∙(1 + z^–1) = 1 + (1 + 1) z^–1 + (1 + 1) z^–2 + …= 1, mod 2;

б) (1 + z^–1 + z^–2 +… + z^–L+1)∙(1 + z^–1) = 1+ (1 + 1)∙z^–1 + … + (1 + 1) z^–L+1 + z^–L =

= 1 + z^–L, mod 2.

В соответствии с (33) схемы запуска принимают вид, показанный на рис.10. Здесь также учтено условие (26) N-кратных интервалов между единицами.

а б

Рис.10

Обратите внимание на подобия и отличия в схемах рис.4, 8 и 10: непрерывную генерацию обеспечивает рекурсивная часть схемы; границы последовательностей задаются нерекурсивной частью; в случае одноразрядных сумматоров (по mod 2) множитель (–1), как отмечалось, опускается.

Работа схем рис.10 моделируется следующими рекуррентными уравнениями:

а) x (k) =  (k) + x (k – 1), mod 2,

k = 0, 1, …; (34)

б) x (k) =  (k) +  (k – LN) + x (k – N), mod 2,

k = 0, 1, … .

В рассмотренных примерах последовательность С_n носила регулярный характер. Для имитации передаваемых сообщений желательно формировать некоторую псевдослучайную импульсную последовательность. Примером может служить так называемая М-последовательность. Кратко рассмотрим способы формирования таких последовательностей.

М-последовательность задаётся рекуррентным соотношением:

С_n = ₁ С_n–1 + ₂ С_n–2 + … + С_n–m, mod 2, (35)

n = 0, 1, …; С_n = 0, n < 0.

Вид последовательности определяется конкретным набором (₁, ₂, …, _m–1) двоичных чисел и значением m.

Примечание. Приведём примеры типичных рекуррентных последовательностей:

• геометрическая прогрессия С_n = q∙С_n–1, n = 0, 1, … , и её вырожденный случай в (33) со знаменателем q = 1 и С₀ = 1;

• числа Фибоначчи в обычной арифметике

С_n = С_n–1 + С_n–2, n = 0, 1, …, С₀ = 1, (это ряд 1, 1, 2, 3, 5, 8, …)

и их двоичный аналог С_n = С_n–1 + С_n–2 , mod 2 , n = 0, 1, … , С₀ = 1,

(это ряд 1, 1, 0, 1, 1, 0 …).

Схема генерации чисел Фибоначчи и ее обобщение рассмотрены в прил. 1.

В силу ограниченности значений  и m всегда можно ожидать, что с некоторого момента n значения С_n начнут повторяться. Это означает, что последовательность (35) обладает периодичностью: С_n = С_n+L. Выбором ко-эффициентов ₁, …, _m–1 (при заданном m) можно обеспечить максимально возможное значение периода

L = 2^m – 1. (36)

Отсюда и название: последовательность максимальной длины. Она включает 2^m–1 единиц и 2^m–1 – 1 нулей. Внешне кажется, что нули и единицы расставлены хаотически с примерно равными вероятностями. В связи с этим такие последовательности называют псевдослучайными.

Фактически (35) является алгоритмом работы генератора М-последовательности. Необходимо только обеспечить запуск этого генератора. Как и во всех рассмотренных выше случаях, для запуска введём единичный отсчёт:

С_n = (n) + ₁∙С_n–1 + ₂∙С_n–2 + … + С_n–m, mod 2 (37)

Теперь начальное значение последовательности определено: С₀ = (0) = 1. Остаётся найти системную функцию генератора.

Перепишем (37), разделив вход и выход знаком равенства:

(n) = С_n + ₁∙С_n–1 + ₂∙С_n–2 + … + С_n–m, mod 2, (37а)

и выполним z-преобразование обеих частей. Пусть D_c(z) – z-преобразование последовательности С_n, n = 0, 1, … : С_n  D_c(z). С учётом свойства (б) z-преобразования

С _n–1  z^–1 D_c(z),

С_n–m  z^–m D_c(z),

для (37а) получим:

D_вх(z) = D_вых(z) = D_c(z)∙(1 + ₁ z^–1 + … + z^–m ).

Z-преобразование левой части в (37а) определено: D_вх(z) = 1. Отсюда следует, что системная функция генератора равна:

(38)

Эта форма реализуется рекурсивной схемой, которая будет генерировать периодическую последовательность двоичных чисел. Как отмечалось, максимального периода L, см. (36), можно достичь только определенными обратными связями (коэффициентами ₁, …, _m–1).

Для генерации М-последовательности без периодического повторения в (37) необходимо ввести дополнительный элемент (n–L). Он задаёт верхнюю границу ряда С_n. В этом случае вместо (37а) запишем:

(n) + (n–L) = С_n + ₁ С_n–1 + ₂ С_n–2 + … + С_n–m, mod 2.

После Z- преобразования получим новую системную функцию генератора:

(39)

Нерекурсивная часть генератора (числитель в (39)) обеспечит формирование М-последовательности заданной длины L.

И последнее замечание. Если выполнить деление числителя на знаменатель в (39), то получим многочлен степени L–m. Это будет системная функция эквивалентного генератора М-последовательности без рекурсивной части.

Примечания: 1. В теории кодирования равенства вида (37а) называют «правилом проверки на чётность»: правая часть должна содержать чётное число единиц, сложение которых (по mod 2) даёт нуль (при n > 0).

2. Значение L по (36) реализуется только при выполнении двух условий: а) степенной полином в знаменателе (38) должен быть «неприводимым», т.е. не представляться множителями; б) этот же полином должен быть «примитивным», т.е. являться делителем двучлена 1 + z^–L (деление в (39) должно быть без остатка). Таблицы таких полиномов для различных степеней m = 2, 3, 4, … можно найти в литературе по кодированию [8].

Рассмотрим все указанные варианты построения генераторов М-последовательностей на примере полиномов степени m = 4. В этом случае L= 15. Запишем все неприводимые множители полинома 1 + z^–15 [8]:

1 + z^–15 = (1 + z^–1)∙(1 + z^–1+ z^–2)∙(1 + z^–3+ z^–4)∙(1 + z^–1+ z^–4)х

х(1 + z^–1+ z^–2+ z^–3 + z^–4), mod 2 . (40)

Здесь только три полинома степени m = 4 (третий, четвертый и пятый). Но последний полином является также и делителем полинома 1+z^–5, см. формулу (33), т.е. он будет порождать последовательность из пяти элементов. Таким образом, для формирования М-последовательности из 15 элементов можно использовать только третий и четвертый полиномы.

Запишем системную функцию генератора в общем виде:

(41)

Соответствующая схема представлена на рис.11. Сумматор здесь – по mod 2.

Рис.11

Схема работает в двух режимах:

а)  = 0 – генерация периодической М-последовательности с L=15 элементами;

б)  = 1 – генерация одного периода М-последовательности.

Коэффициенты  устанавливаются в соответствии с порождающим полиномом. В первом варианте (для полинома 1 + z^–3 + z^–4) имеем: ₁ = 0, ₃ = 1. Схема генерирует последовательность С_n по алгоритму:

С_n = (n) + С_n–3 + С_n–4 , mod 2, n =0, 1, … .

В результате получим (для одного периода):

С_n = (1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0) . (42)

Во втором варианте (для полинома 1 + z^-1 + z^–4) имеем ₁=1, ₃=0. Схема рис.11 формирует последовательность С_n по алгоритму:

С_n = (n) + С_n–1 + С_n–4 , mod 2, n =0, 1, … .

Результатом (для одного периода) будет:

С_n = (1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0). (43)

Как отмечалось, схему генератора можно реализовать и в нерекурсивном варианте. Для этого достаточно составить цепочку из 12 элементов сдвига z^–1 и объединить ее вход и выходы в соответствии с ненулевыми позициями кода (42) или (43). Последние три позиции дополняются искусственно. Ясно, что ценность таких схем мала, особенно для больших значений L.

Для перевода генератора М-последовательности в схему запуска необходимо заменить элементы z^–1 и z^–L на z^–N и z^–LN (как на рис.9 и 10). В результате получим последовательность редких импульсов X(k):

следующих с интервалом в N тактов. При этом символические значения кода С_n (1 или 0) переводятся в однополярные импульсы.

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

. (44)

Теперь последовательность будет менять знак в соответствии с кодом С_n.

Различия этих разновидностей импульсов можно заметить на примере запуска генератора «радиоимпульсов» (см. рис. 6). Однополярный запуск имитирует кодированный АМ-сигнал, а двухполярный – кодированный ФМ-сигнал.