Коды сдвигового регистра максимальной длины

 (m -последовательности)

Эти коды относятся к классу ЦК (n, k) = (2 ^m – 1, т), где т положительное число, соответствующее числу информационных бит.

Кодовые слова генерируются m - каскадным регистром сдвига с обратной связью, построенным по проверочному полиному.   

В таблице 3.3 [3] даны номера ячеек регистра сдвига для 2 ≤ т ≤34, которые объединяются в сумматоре по mod 2.

 

                  Таблица 3.3. Параметры кодеров т- последовательности.

m	№№ отводов к сумматору по модулю 2	m	№№ отводов к сумматору по модулю 2	m	№№ отводов к сумматору по модулю 2	m	№№ отводов к сумматору по модулю 2
2	1, 2	11	1, 10	20	1, 18	29	1, 28
3	1, 3	12	1, 7, 9, 10	21	1, 20	30	1, 8, 29, 30
4	1, 4	13	1, 10, 11, 13	22	1, 22	31	1, 29
5	1, 4	14	1, 5, 9, 14	23	1, 19	32	1, 11, 31, 32
6	1, 6	15	1, 15	24	1, 18, 23, 24	33	1, 21
7	1, 7	16	1, 5, 14,16	25	1, 23	34	1, 8, 33, 34
8	1, 5, 6, 7	17	1, 15	26	1, 21, 25, 26
9	1, 6	18	1, 12	27	1, 23, 26, 27
10	1, 8	19	1, 15, 18, 19	28	1, 26

 

Например, для т=3 трехкаскадный генератор дан на рис.3.10.

 

Рис.3.10. Кодер ЦК т - последовательности при т=3.

 

Для каждого передаваемого кодового слова сначала вводятся в РС т  информационных бит (старшими разрядами вперед) и ключ переводится в положение 2. Содержимое РС сдвигается влево по тактам n = (2 ^m – 1) раз и на выходе получают систематический ЦК - слово длины п. Для каждого из входных (2 ^m – 1) информационных блоков (за исключением нулевого) все генерируемые кодовые слова длины п представляют собой циклические сдвиги одного кодового слова. Поэтому выходная последовательность кодера периодическая с максимально возможным периодом   п = (2 ^m – 1).

Каждое из этих (2 ^m – 1)  кодовых слов содержит 2^т-1 единиц и 2^т-1 нулей (код равновесный). Поскольку код линейный, то его вес является минимальным расстоянием кода                                                                                   d_min = 2^т-1.                                 (3.45)

Автокорреляционная функция r (m) такой равновесной периодической кодовой последовательности является периодической со значениями:

r (m) = п при т=0,±п, ±2п; …                  (3.46)

   r (m) = −1 для других сдвигов.

Следовательно, спектр мощности т - последовательности близок к равномерному. Эти псевдошумовые последовательности проявляют свойства белого шума, имеют максимально возможный период и применяются для скремблирования данных и генерации ШПС с расширенным спектром.

Коды т - последовательности являются дуальными кодами для циклических кодов Хемминга (2 ^m – 1, 2 ^m – 1- т).

3.1.4.4.  Недвоичные линейные блоковые коды

Рида - Соломона.

Коды РС составляют подкласс недвоичных блоковых БЧХ циклических кодов с фиксированной длиной кодовых слов. Каждый элемент кодового слова выбирается из алфавита поля Галуа GF (q =2 ^k), содержащего q символов {0,1,2,… q −1}. Кодируемые k информационных бит группы отображаются одним из q символов и его называют информационным символом. Длина недвоичного кодового слова - N. Число информационных символов, закодированных в кодовом слове из N символов, обозначают К.

Систематический линейный блоковых код РС (N, K) содержит К информационных символов (групп) и (N − K) проверочных символов. Эти коды описываются параметрами:

N = q −1 = 2 ^k −1;

K = 1,2,3,.. N −1;                                 (3.47)

D_min = N − K +1,

где D_min - минимальное кодовое расстояние.

Такой код исправляет t  символов с ошибкой:

.           (3.48)

Код РС хорошо согласован с М - ичной модуляцией, например, М-ичной ЧМ для передачи q =2 ^k возможных символов. Каждый из q символов отображается в один из М = 2 ^k ортогональных сигналов.

Если демодулятор выносит жесткие решения, то вероятность ошибки символа Р _м (соответствующего k информационным битам) и параметры кода достаточны для характеристики декодера. Действительно, модулятор, канал с АБГШ и демодулятор образуют эквивалентный симметричный канал без памяти с дискретным (М - ичным) входом и дискретным (М - ичным) выходом.

Эта модель с переходными вероятностями для символов Р_с=1−Р_м и ошибок  представлена на рис.3.11.

 

Рис.3.11. Модель дискретного симметричного канала без памяти с

М - ичными входом и выходом.

v

Качество декодера жестких решений можно оценить верхней границей для вероятности ошибки кодового слова кода РС (3.9.):

.                                (3.49)

Этой ошибке слова соответствует средняя на символ вероятность ошибки            

.           (3.50)

При k бит в символе известна вероятность ошибки на бит:                                                             (3.51)

Пример. Найти вероятность ошибки на бит для кода РС с параметрами: k =5, N =2⁵−1=31, D_min =3,5,9,17.

Решение.

Соответствующие   D_min значения K согласно (3.47) равны 29,27,23,15, а t согласно (3.48) равны 1,2,4,8. При модуляции используем М = q =32 ортогональных ЧМ сигналов и некогерентный прием. Вероятность приема символа М-ичной ЧМ [3]:                  

,                     (3.52)

где γ - ОСШ на кодовый символ.

Подставляя Р _м в (3.50) и полученный результат в (3.51) получим зависимость вероятности ошибки на бит от ОСШ.

Сверточное кодирование

 

Сверточный код (СК) генерируется кодером на основе линейного РС с конечным числом состояний рис. 3.12.

 

Рис.3.12. Обобщенная схема кодера СК.

 

В общем случае кодер состоит из K (k -битовых) ячеек РС и n функциональных генераторов линейного преобразователя, выполняющего алгебраические функции по mod 2.

Входные информационные данные кодера (в двоичной форме) продвигаются вдоль регистра сдвига по k бит за один такт. Число выходных битов для каждой k - битовой входной последовательности равно n. Следовательно, кодовая скорость R_c = k / n согласуется с определением скорости блокового кода.

Параметр К называется кодовым ограничением СК, которое определяют:

-чаще всего при k =1 числом К-1;

-во многих случаях в битах, а не в k - битовых блоках и РС называют L - ячеечным РС, где L = K k; в общем случае L может и не быть кратным К.

3.2.1. Методы задания СК

    СК можно задать:

1. Порождающей матрицей, как и для блоковых кодов. В общем

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

2. Эквивалентным набором из n векторов g _i, i =1,2… n; один вектор для каждого из n сумматоров по mod 2.

Каждый вектор имеет размерность K ∙ k и содержит информацию о соединениях РС с сумматорами по mod 2. Единица в i - й позиции вектора указывает на подключение ячейки РС к сумматору по mod 2, а нуль в данной позиции указывает на отсутствие этого подключения.

 

Пример 1. Пусть задан  двоичный свёрточный кодер с кодовым ограничением K = 3 при k = 1, n = 3, рис.3.13.

 

Найдем вектора g _i, задающие СК.

Пронумеруем функциональные генераторы и их выходы в соответствии с порядком считывания мультиплексором (1,2,3). С первым функциональным генератором соединена только первая ячейка РС (сумматор по mod 2 не нужен) и этот генератор можно задать вектором: g ₁ = [100]. Второй функциональный генератор соединён с ячейками 1 и 3, следовательно, g₂ = [101], а g₃ = [111].

В результате кодер генерирует СК, определяемый векторами g _i.

В исходном состоянии все ячейки РС находятся в нулевом состоянии. Допустим, что первый входной бит «1». Он без задержки появится на выходе первой (левой) ячейки регистра и, соответственно, на всех трёх входах выходного ключа (мультиплексора). Ключ поочередно выдаёт содержание входов, и выходная последовательность состоит из трёх бит 111. Допустим, что второй входной бит «0». Он записывается в первую ячейку регистра и проталкивает предыдущий бит «1» во вторую ячейку – и на выходе мультиплексора сверху вниз появляется «0», «0» и «1». Т. е. вторая выходная последовательность 001. Если третий входной бит «1», то выходная последовательность 100 – и т.д. Таким образом, в ответ на каждый входной бит (при k =1) свёрточный кодер откликается тремя битами (по числу функциональных генераторов n =3).

Совокупность n генераторов (порождающих полиномов), обычно  задают в восьмеричной форме как g = (4,5,7). Таким образом, чтобы задать кодер при k =1 требуется n генераторов, каждый размерностью К. В общем случае при k >1 и кодовом ограничении К эти n генераторов отображаются К k -мерными векторами g _i.

 

Пример 2.  Пусть задан сверточный кодер рис.3.14.

 

 

Рис. 3.14.  Сверточный кодер с параметрами:   К=2, k=2, n =3.

 

СК имеет скорость кода 2/3. В кодере каждый такт поступают два бита на вход регистров сдвига, а на выходе генерируется 3 бита. Генераторы определяются векторами: g₁=[1011], g₂=[1101], g₃=[1010].  В восьмеричной форме g = (13, 15, 12).

 

3.2.2. Методы описания СК

Имеется три метода, используемые для описания СК: древовидная диаграмма, решетчатая диаграмма и диаграмма состояния.

Древовидная диаграмма для кодера Рис. 3.13 с параметрами   К=3, k =1, n =3 приведена на рисунке 3.15. Предположим, что кодер находится первоначально в нулевом состоянии (нули во всех ячейках). Диаграмма показывает, что если первый входной бит 0, то выходная последовательность 000.

 

Рис.3.15 Древовидная диаграмма для СК со скоростью 1/3     

 (К=3, k=1, n=3).

 

Если первый входной бит «1» - выходная последовательность –111. Теперь, если первый входной 1, а второй 0 – то второй набор выходных битов 001. Продвигаясь по дереву состояний видим, что если третий входной бит 1, то выход 100.

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

Таким образом, траектория частного пути по дереву определяется входной последовательностью. Из анализа дерева видно, что структура повторяет себя после третьего такта. Правый столбец выходных «троек» бит распадается на две одинаковые совокупности по восемь троек. Это поведение согласуется с тем фактом, что кодовые ограничения К=3. Это значит, трёх - битовые выходные последовательности на каждом такте определяются входным битом и двумя предыдущими входными битами, т.е. двумя битами, содержащимися в первых двух ячейках РС. Бит в последней ячейке регистра сдвига перемещается направо (покидает регистр) и не влияет больше на выход. Можно сказать, что трёх - битовая последовательность выхода для каждого входного бита определяется входным битом и четырьмя возможными состояниями РС, обозначенными а=00, b =01, с=10, d =11. Если пометить узлы дерева этими же метками, найдём, что на третьем такте имеется два узла с пометкой «а», два с пометкой «b», два с пометкой «с» и два с пометкой «d». Теперь видим, что все ветви, исходящие из двух узлов с одинаковой меткой (с одинаковым состоянием) генерируют одинаковые выходные последовательности. Это означает, что два узла, имеющие одинаковую метку, можно слить и получить решетчатую диаграмму, рис 3.16.

 

Рис. 3.16.  Решетчатая диаграмма для СК со скоростью 1/3 (К=3, k=1, n=3).

 

    Согласно правому столбцу (рис.3.15) в исходном нулевом состоянии РС:

- на такте t ₁ (рис.3.16) из состояния «а» генерируются (в зависимости от входного бита) две последовательности: «000» и «111», которые определяют состояния «а» и «с»;

- на такте t ₂ из состояния «с» генерируются «001» и «110», которые определяют состояния «b» и «d» соответственно, из которых генерируются соответственно:

-из «b» → «011», который определяет переход в состояние «а»;

       → «100», который определяет переход в состояние «с»;

-из «d» → «010», который определяет переход в состояние «b»;

      → «101», который определяет переход в состояние «d» и т. д.

Поскольку выход кодера определяется входом и состоянием кодера, ещё более компактной, чем решётка является диаграмма состояний, рис.3.17.

 

 

Рис.3.17. Диаграмма состояний для СК со скоростью 1/3 (К=3, k=1, n=3).

 

    Если обозначить α β переход из состояния α в β, когда входной бит 1, то эта диаграмма показывает, что возможные переходы таковы:

а а, а с, b а, b с, с b, с d, db, d d.

Три бита, показанных на каждой ветви диаграммы состояний, представляют выходные биты кодера. Пунктирная линия на графе означает, что входной бит 1, а сплошная линия - бит ноль.

Найдем распределение весов и кодовое расстояние для СК.

 

3.2.3. Передаточная функция СК

    Так как СК линейный, то набор расстояний Хемминга между кодовы-

последовательностями (КП), генерируемыми на определённом шаге дерева, определяется относительно КП из одних нулей. Пусть входом кодера является нулевая последовательность. Пометим ветви на диаграмме состояний рис. 3.17 как D⁰, D¹, D² и D³. Показатель у D означает расстояние Хемминга между выходной КП соответствующей ветви и выходной КП ветви из одних нулей. Собственную петлю у узла «а» можно исключить. Далее узел «а» расщепим на два узла, один из которых представляет вход «а», а другой выход «е» состояния и получим диаграмму рис. 3.18.

 

Рис.3.18.  Диаграмма состояний для СК со скоростью 1/3 (К=3, k=1, n=3).

 

Для этой диаграммы можно написать четыре уравнения состояния:

 

 Х_с= D ³ Х_а+ D Х _b;    Х _b = D Х_с+ D Х _d;

        Х _d = D ² Х_с+ D ² Х _d;   Х_е= D ² Х _b.                                   (3.53)

 

Передаточная функция кода определяется как Т(D)=Х_е /Х_а .

Решив эти уравнения относительно Х _e и Х _a и произведя деление полиномов, получим:

Т(D) = D ⁶ /(1-2 D ²) = D ⁶ +2 D ⁸ +4 D ¹⁰ +8 D ¹² + …=,    (3.54)

где, число путей с расстоянием d равно

a_d =;                                    (3.55)

D⁶         | 1-2 D²

D⁶-2 D⁸           D⁶+2D⁸+4 D¹⁰+

2D⁸

2 D⁸-4 D¹⁰

4D¹⁰

4 D¹⁰-8 D¹²

 8D¹² и т.д.

Передаточная функция этого кода показывает, что имеется единственный путь с расстоянием Хемминга d =6 от пути из одних нулей, который сливается с путём из одних нулей при данном узле. Из диаграммы состояний рис. 3.18 видно, что путь с d =6 – это путь ас b е. Нет других путей из узла «а» до узла «е», имеющих d =6.

Второе слагаемое в (3.54) указывает, что есть два пути от узла «а» до узла «е», имеющих расстояние d =8. Из диаграммы состояний и решётки видно, что этими путями являются: а с d b е и а с b с b е.

Третье слагаемое указывает, что есть четыре пути с расстоянием d =10 и т.д. Таким образом, передаточная функция дает дистанционные свойства СК.

    Минимальное расстояние кода называется минимальным свободным расстоянием СК и обозначается d _св. Для данного СК d _св =6.

Передаточная функция СК дает более детальную информацию о путях, чем только кодовое расстояние между различными путями СК. Покажем это.

Введем множитель N для всех переходов (пересечений) ветвей, вызванных входным битом 1. Тогда, поскольку каждая ветвь пересекается, совокупный показатель N увеличивается на 1 только тогда, когда переход ветви обусловлен входным битом 1. Далее введем множитель J для каждой ветви диаграммы состояний, а показатель у J будет служить счётной величиной, указывающей число ветвей для любого данного пути от узла «а» к узлу «е». Тогда, в нашем примере диаграмма для СК со скоростью 1/3 примет вид рис.3.19.

 

Рис. 3.19. Диаграмма состояний для СК со скоростью 1/3 (К=3, k=1, n=3).

 

Уравнения состояний для диаграммы рис. 3.19.  имеют вид:

 

Х_с =JND³ Х_а +JND Х _b; Х _b =JD Х_с +JD Х _d;

Х _d = JND ² Х _c + JND ² Х _d;      Х_е= JD ² Х _b                        (3.56)

Решая эти уравнения и производя деление, получим передаточную функцию:

Т( D, N, J)= J ³ ND ⁶ /(1- JND ² (1+ J))= J ³ ND ⁶ + J ⁴ N ² D ⁸ + J ⁵ N ² D ⁸ + J ⁵ N ³ D ¹⁰ +  

 +2 J ⁶ N ³ D ¹⁰ + J ⁷ N ³ D ¹⁰ +…

Эта форма передаточной функции даёт более детальные характеристики всех путей СК. Первое слагаемое в выражении Т(D, N, J) указывает на то, что путь с расстоянием d =6 имеет длину 3 и что из трёх информационных бит один равен 1. Второе и третье слагаемые в выражении Т(D, N, J) указывает на то, что из двух слагаемых с d =8 одно будет длиной 4, а второе длиной 5.Два из четырёх информационных бит в пути длиной 4 и два из пяти информационных бит в пути длиной 5 является «1».

Таким образом:

- показатель множителя J указывает длину пути, который сливается первый раз с путем из одних нулей;

- показатель множителя N указывает число «1» в информационной последовательности для этого пути;

- показатель D указывает расстояние от последовательности кодированных бит этого пути до последовательности с одними нулями.