- •«Теория кодирования»
- •Первичные коды и эффективное кодирование
- •Префиксные коды
- •Примерами префиксных кодов являются коды Шеннона-Фано и Хаффмана. Код Шеннона-Фано
- •Код Хаффмана
- •Кодирование факсимильных изображений. Коды кдс-1, кдс-2, кдс-3
- •Основные параметры помехоустойчивых кодов
- •Классификация помехоустойчивых кодов
- •Коды: общие сведения, основные свойства
- •Линейные блоковые коды
- •Условия и свойства формирования разрешенных кодовых последовательностей лбк
- •Задание линейных кодов с помощью порождающих и проверочных матриц
- •Кодирование информации линейным блоковым кодом
- •Синдромное декодирование
- •Мажоритарное декодирование
- •Циклические коды: общие сведения, определение
- •Свойства циклических кодов
- •Способ построения кодовых последовательностей с использованием порождающей матрицы
- •Назначение и способы построения проверочной матрицы циклического кода
- •Способ формирования кодовых последовательностей циклического кода с использованием образующего полинома
- •Многотактные фильтры
- •Кодирование информации циклическими кодами
- •Декодирование информации циклическими кодами
- •Синдромный метод декодирования цк
- •I Табличное синдромное декодирование
- •II Схемное синдромное декодирование
- •Многомерные коды: определение, классификация
- •Матричные коды: определение, принцип построения, свойства, параметры, достоинства и недостатки
- •Итеративные коды: определение, принцип построения, основные характеристики
- •Каскадные коды: определение, принцип построения, основные характеристики
- •Сверточные коды: определение, параметры, классификация
- •Задание систематических сверточных кодов
- •I. Задание систематических ск с помощью порождающей матрицы g(х)
- •II. Задание систематических ск с помощью проверочной матрицы h(х)
- •III. Задание систематических ск с помощью разностных треугольников
- •Кодирование информации сверточными кодами
- •Структурная схема кодера
- •Жесткое пороговое декодирование сск
- •Мягкое пороговое декодирование сск
- •Многопороговое декодирование сск
- •Структурная схема декодера
- •Список литературы
Задание линейных кодов с помощью порождающих и проверочных матриц
Линейные коды задаются с помощью порождающей G(x)и проверочнойH(x)матриц. Эти матрицы связаны основным уравнением кодирования:
G(x)H(x)T=0.
Матрица G(x)содержитkстрок иnстолбцов, ее элементами являются нули и единицы. В качестве строк матрицыG(x)выбираются любые ненулевые линейно независимыеn-значные векторы, отстоящие друг от друга не менее чем на заданное кодовое расстояниеd0.
Векторы v1,v2, …,vkназываютсялинейно независимыми, если выполняется условие
c1 v1 + c2 v2 +…+ck vk = 0,
где сi={0, 1}, а сложение выполняется по модулю два. То есть, каким бы образом мы не суммировали различные строки матрицыG(x), не получим суммы, равной нулю. Все множество кодовых слов состоит из строк порождающей матрицы и всевозможных комбинаций этих строк, т.е. суммы по модулю два всех строк матрицыG(x)сначала попарно, затем по три и так далее до суммы всехkстрок.
С точки зрения алгебры все кодовые слова образуют некоторое векторное пространство, базисом которого являются строки матрицы G(x).
Поскольку линейно независимые векторы могут быть выбраны произвольным образом, то, очевидно, можно построить множество матриц G(x)с одним и тем же кодовым расстояниемd0.
Свойство линейной независимости векторов инвариантно относительно двух следующих операций (выполняя эти две операции, кодовое расстояние не меняется):
возможна произвольная перестановка строк и столбцов в матрице G(x);
замена i-й строки на суммуi-й иj-й строк и т. д. (эту операцию нельзя осуществлять со столбцами матрицыG(x)).
Производя вышеуказанные операции, любую произвольную матрицу G(x)можно привести к так называемомуприведенно-ступенчатому(каноническому)виду:
n
где Ik – единичная подматрица размерностьюk×k,
H*T – транспонированная проверочная матрица (транспонировать – значит поменять местами строки и столбцы).
Исходя из основного уравнения кодирования, проверочная матрица имеет вид
l
n
Пример:
Возьмем порождающую матрицу кода (7,4). В этой матрице количество строк равно 4 (k=4), а количество столбцов 7(n=7).
1 0 0 0 1 0 1
G(x)=0 1 0 0 1 1 1
0 0 1 0 1 1 0
0 0 0 1 0 1 1
Для того чтобы построить проверочную матрицу, необходимо транспонировать подматрицу G(x)*и к ней приписать единичную матрицу размеромl×l. Проверочная матрица будет иметь размерl×n,l =n-k=7-4=3, т.е. матрица Н(x) имеет размер 3×7.
1 1 1 0 1 0 0
H(x)=0 1 1 1 0 1 0
1 1 0 1 0 0 1
Кодирование информации линейным блоковым кодом
Операция кодирования информации линейным кодом заключается в умножении информационного вектора Akразмерностьюkна порождающую матрицуG(x); в результате получаем вектор
F(x)=Ak(x)G(x).
Кодовую последовательность на выходе кодера можно записать в виде:
где a1a2a3...аk- информационные символы (логические 1 и 0),
b1b2b3...b1- проверочные символы (логические 1 и 0).
Проверочные символы b1b2b3...blформируются путем суммирования по модулю два информационных символов, стоящих на определенных позициях.
Алгоритм формирования проверочных символов в общем виде можно записать так:
где cj1cj2...cjk- коэффициенты принимающие значение логических 1 и 0.
Пример:Ak(x)=1010
1 0 0 0 1 0 1
G(x)=0 1 0 0 1 1 1
0 0 1 0 1 1 0
0 0 0 1 0 1 1
1 0 0 0 1 0 1
Следовательно, F(x)=Ak(x)G(x)=[1010]* 0 1 0 0 1 1 1 = [1010 011]
0 0 1 0 1 1 0
0 0 0 1 0 1 1
Рассмотрим построение и реализацию устройства кодирования ЛБК (7,4).
Порождающая и проверочная матрицы этого кода имеют вид:
а1а2а3а4 b1b2b3
1 0 0 0 1 0 1 1 1 1 0 1 0 0
G(x)=0 1 0 0 1 1 1 H(x)=0 1 1 1 0 1 0
0 0 1 0 1 1 0 1 1 0 1 0 0 1
0 0 0 1 0 1 1
Этот код имеет d=3 и исправляет все одиночные ошибки и обнаруживает двойные. Символы а1,а2,а3,а4 – информационные символы, b1,b2,b3 – проверочные.
По матрице запишем проверочные уравнения:
b1= a1a2a3
b2= a2a3a4
b3= a1a2a4
Таким образом, кодер состоит из (n-k)=7-4=3 сумматоров по модулю два, выходы которых соответствуют (n-k) проверочным символам.
Устройство кодирования линейного группового кода (7, 4) приведено на рисунке.
Рисунок – Кодер линейного группового кода (6, 3)
Пусть подается сообщение (а1,а2,а3,а4)=1001. Тогда слово, передаваемое в канал связи, имеет вид (1001 110).