- •«Теория кодирования»
- •Первичные коды и эффективное кодирование
- •Префиксные коды
- •Примерами префиксных кодов являются коды Шеннона-Фано и Хаффмана. Код Шеннона-Фано
- •Код Хаффмана
- •Кодирование факсимильных изображений. Коды кдс-1, кдс-2, кдс-3
- •Основные параметры помехоустойчивых кодов
- •Классификация помехоустойчивых кодов
- •Коды: общие сведения, основные свойства
- •Линейные блоковые коды
- •Условия и свойства формирования разрешенных кодовых последовательностей лбк
- •Задание линейных кодов с помощью порождающих и проверочных матриц
- •Кодирование информации линейным блоковым кодом
- •Синдромное декодирование
- •Мажоритарное декодирование
- •Циклические коды: общие сведения, определение
- •Свойства циклических кодов
- •Способ построения кодовых последовательностей с использованием порождающей матрицы
- •Назначение и способы построения проверочной матрицы циклического кода
- •Способ формирования кодовых последовательностей циклического кода с использованием образующего полинома
- •Многотактные фильтры
- •Кодирование информации циклическими кодами
- •Декодирование информации циклическими кодами
- •Синдромный метод декодирования цк
- •I Табличное синдромное декодирование
- •II Схемное синдромное декодирование
- •Многомерные коды: определение, классификация
- •Матричные коды: определение, принцип построения, свойства, параметры, достоинства и недостатки
- •Итеративные коды: определение, принцип построения, основные характеристики
- •Каскадные коды: определение, принцип построения, основные характеристики
- •Сверточные коды: определение, параметры, классификация
- •Задание систематических сверточных кодов
- •I. Задание систематических ск с помощью порождающей матрицы g(х)
- •II. Задание систематических ск с помощью проверочной матрицы h(х)
- •III. Задание систематических ск с помощью разностных треугольников
- •Кодирование информации сверточными кодами
- •Структурная схема кодера
- •Жесткое пороговое декодирование сск
- •Мягкое пороговое декодирование сск
- •Многопороговое декодирование сск
- •Структурная схема декодера
- •Список литературы
III. Задание систематических ск с помощью разностных треугольников
Разностный треугольник представляет собой совокупность целых, действительных и неповторяющихся чисел, записанных в форме треугольника. Для ССК с R = k0/n0 количество разностных треугольников равно числу k0. Для всех разностных треугольников общим числом является “0”, который не указывается в совокупности чисел, однако учитывается при выборе степеней ненулевых членов порождающих полиномов. Степени ненулевых членов порождающих полиномов по заданным или построенным разностным треугольникам можно найти путем выбора чисел:
левого крайнего столбца разностного треугольника, считывая их сверху вниз и дополняя числом “0”,
верхней строки разностного треугольника в такой последовательности: первое число – показатель степени второго ненулевого члена порождающего полинома; суммирование первого и второго чисел первой строки разностного треугольника определяет показатель степени третьего ненулевого члена порождающего полинома и т.д.
Пример: Определить параметры ССК с алгоритмом ПД при следующем разностном треугольнике:
Так как задан один разностный треугольник, то k0=1, n0=k0+1=2, , код имеет один порождающий полином.
Выписывая числа левого крайнего столбца разностного треугольника, определяем показатели степеней порождающего полинома: (0,2,6,7). Следовательно, порождающий полином ССК имеет вид: g(х)=1+x2+x6+x7. При втором способе –0; 2; 2+4=6; 2+4+1=7. Как правило, в литературе разностные треугольники табулированы и представлены, например, так: ((2,4,1), (3,5,2)). Это означает, что ССК имеет соответственно параметры: k0=2, n0=k0+1=3, иg1(x)=1+x2+x6+x7 и g2(x)=1+x3+x8+x10.
Разностный треугольник ССК может быть построен, если задан проверочный треугольник, и наоборот.
Пример: По проверочному треугольнику построить разностный.
Числа крайнего левого столбца разностного треугольника определяются как результат операции вычитания порядковых номеров строк проверочного треугольника, которые начинаются с “1”. Для первого столбца получаем следующие числа: 3–1=2 (3 – номер позиции третьей строки, 1 – номер позиции первой строки); 7–1=6 и 8–1=7. Для получения чисел второго столбца за вычитаемое берем номер позиции третьей строки: 7–3=4 и 8–3=5. Для получения чисел третьего столбца за вычитаемое берем номер позиции седьмой строки: 8–7=1.
Числа, входящие в разностные треугольники, должны быть целыми, действительными и неповторяющимися. Только в этом случае будет сформирована система ортогональных (раздельных) проверок. Для получения совокупности таких чисел известно достаточно много способов их нахождения, но наиболее эффективным является способ, основанный на теории совершенных разностных множеств.
Задание систематических СК с использованием
совершенных разностных множеств
Совершенное разностное множество – это совокупность целых, действительных и неповторяющихся чисел 1, 2, … , причем 1<2< и разности этих чисел полученных по некоторому mod (2), также образующих совокупность целых, действительных и неповторяющихся чисел.
Данную совокупность полученных разностных чисел можно использовать в качестве исходных чисел для формирования разностных треугольников и выбора соответствующих порождающих полиномов ССК.
При выборе чисел для построения разностных треугольников необходимо выбирать числа с наименьшим их значением по номиналу, т.к. максимальное значение числа в построенных разностных треугольниках определяет максимальную степень m порождающих полиномов ССК.
Рассмотрим построение ССК с алгоритмом ПД с использованием совершенных разностных множеств.
Пусть, например, имеется совокупность =3-х целых, действительных и неповторяющихся чисел (=1,2,3) и эта совокупность образует 2+=32+3=12 разностей по модулю 2++1=32+3+1=13, которые равны следующим числам:
1 – 01 |
12 – 84 |
2 – 87 |
0 – 31 |
3 – 12 |
0 – 85 |
8 – 08 |
1 – 311 |
3 – 03 |
8 – 26 |
8 – 129 |
0 – 112 |
Полученную совокупность разностных чисел можно разбить на следующие подмножества:
-
1
2
6
4
3
8
10
5
9
12
11
7
.
j
Каждый из столбцов данного множества можно использовать для построения разностного треугольника. Следовательно, можно построить k0=4 разностных треугольника и четыре ССК с, сJ=4 и с сJ=5, разбив данное множество на три подмножества.
Отметим, что с использованием теории совершенных разностных множеств были рассчитаны и табулированы показатели степеней ненулевых членов порождающих полиномов ССК с дляJ=2…16.