Общее число всевозможных комбинаций кода длины n равно: Nn=2n. Число разрешенных кодовых комбинаций определяется числом информационных разрядов и равно: Nk=2k=2n-r, где r - число проверочных разрядов. Таким образом, число разрешенных кодовых комбинаций в 2r раз меньше общего числа комбинаций.
| 3.2. Классификация и характеристики корректирующих кодов. |
Корректирующие коды делятся на два класса - блочные и непрерывные. К блочным относятся коды, в которых каждому символу алфавита сообщений соответствует блок (кодовая комбинация) из n(i) элементов, где i – номер сообщения. Если n(i)=n, т.е. длина блока постоянна и не зависит от номера сообщения, то код называется равномерным. Если длина блока зависит от номера сообщения, то блочный код называется неравномерным. При использовании блочных кодов передаваемая информационная последовательность разбивается на отдельные блоки, которые кодируются и декодируются независимо друг от друга. Непрерывные коды представляют собой непрерывную последовательность разрядов, и разделение ее на отдельные блоки невозможно. В таких кодах проверочные элементы помещаются в определенном порядке между информационными.
Блочные коды, в свою очередь, делятся на разделимые и неразделимые. Разделимыми называются коды, в которых элементы разделяются на информационные и проверочне. Последние и вносят в код избыточность, необходимую для обнаружения или исправления ошибок. В разделимых кодах информационные и проверочные разряды занимают всегда одни и те же позиции в кодовой комбинации. Разделимые коды обозначаются как (n, k) - коды, где n - длина или число разрядов кода; k - число информационных разрядов. Неразделимые коды свойством разделимости не обладают.
Среди разделимых кодов различают коды систематические и несистематические. Систематическими называются такие блочные разделимые коды, в которых проверочные разряды представляют собой линейные комбинации информационных.
Основными характеристиками корректирующих кодов являются:
| 3.3. Циклические коды. |
Циклические коды обеспечивают обнаружение и исправление, как независимых ошибок (одиночных и многократных), так и пачек ошибок. Циклические коды обладают двумя важными свойствами. Во-первых, сумма по модулю два любых двух разрешенных комбинаций циклического кода также является разрешенной кодовой комбинацией. Отсюда следует, что наименьшее кодовое расстояние в циклическом коде определяется наименьшим весом его комбинаций. Во-вторых, если в разрешенной кодовой комбинации осуществить циклическую перестановку элементов этой комбинации, то в результате получится другая разрешенная кодовая комбинация, принадлежащая данному коду.
Циклические коды относятся к блочным систематическим кодам. Код Хэмминга, исправляющий одиночные ошибки, представляет собой частный случай циклического кода.
Введем следующие обозначения:
G(x) - многочлен, отображающий комбинацию информационных элементов (степень многочлена - k-1);
R(x) - многочлен, отображающий комбинацию из r проверочных элементов;
F(x) - многочлен, отображающий кодовую комбинацию в целом (степень многочлена - n-1=k+r-1);
F(x) = xrG(x) + R(x).
Комбинация циклического кода F(x) образуется из исходной комбинации информационных разрядов G(x) путем умножения на полином P(x). Поэтому полином Р называется образующим. Разрешенные кодовые комбинации циклического кода характеризуются тем, что все они делятся без остатка на образующий полином P(x). Это условие выполняется, если R(x) равен остатку от деления xrG(x) на Р(x).
Обнаруживающие ошибки свойства циклического кода основаны на том, что разрешенные комбинации кода F(x) делятся на образующий полином P(x) без остатка, а запрещенные - с остатком.
Комбинации циклического кода формируются следующим образом:
| 4. АНАЛИЗ ВОЗМОЖНОСТЕЙ ЗАДАННОГО ЦИКЛИЧЕСКОГО КОДА. |
| 4.1. Составление порождающей матрицы и матрицы проверок. |
Образующий полином : p(x) = x10+x9+x7+x1+1
Составим образующую матрицу в неканоническом виде G(15,5):
| x4 | * P(x) | x14+x13+x11+x5+x4 | 11010 0000110000 | |||
| x3 | * P(x) | x13+x12+x10+x4+x3 | 01101 0000011000 | |||
| G(15,5) = | x2 | * P(x) | = | x12+x11+x9 +x3+x2 | = | 00110 1000001100 |
| x1 | * P(x) | x11+x10+x8 +x2+x1 | 00011 0100000110 | |||
| x0 | * P(x) | x10 +x9 +x7 +x1 +1 | 00001 1010000011 |
Далее составим образующую матрицу в каноническом виде G(15,5):
| Номера строк, которые необходимо сложить по модулю 2 | G(15,5) = |E(5,5) R(5,10)| |
| 1+2+3+5 | 10000 0010100111 |
| 2+3+4 | 01000 1100010010 |
| 3+4+5 | 00100 0110001001 |
| 4+5 | 00010 1110000101 |
| Переписываем | 00001 1010000011 |
Матрица проверок H(15,5) :
| 01011 1000000000 | |
| 01110 0100000000 | |
| 10111 0010000000 | |
| 00000 0001000000 | |
| H(15,5) = |RT(10,5) E(10,10)| = | 10000 0000100000 |
| 01000 0000010000 | |
| 00100 0000001000 | |
| 10010 0000000100 | |
| 11001 0000000010 | |
| 10111 0000000001 |
| 4.2 Определение минимального кодового расстояния. |
Минимальное кодовое расстояние равняется минимальному количеству столбцов матрицы H(15,5), при сложении которых по модулю 2, получается столбец, состоящий из всех нулей.
Для определения минимального кодового расстояния dmin воспользуемся матрицей проверок H(15,5):
| 01011 1000000000 | |
| 01110 0100000000 | |
| 10111 0010000000 | |
| 00000 0001000000 | |
| H(15,5) = |RT(10,5) E(10,10)| = | 10000 0000100000 |
| 01000 0000010000 | |
| 00100 0000001000 | |
| 10010 0000000100 | |
| 11001 0000000010 | |
| 10111 0000000001 |
Для данной матрицы проверок при сложении столбцов (выделенных на матрице жирным шрифтом) по модулю 2, мы получим столбец, состоящий из всех нулей. Таким образом, для данного образующего полинома:
Р(х) = x10 +x9 +x7 +x1 +1, минимальное кодовое расстояние равно 5.
| 4.3. Составление таблицы всех ненулевых разрешенных кодовых комбинаций и определение их веса. |
| Число вариан-тов | № | №№ строк G(15,5) | Информационные элементы | Проверочные элементы | Вес w | |||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | ||||
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 6 | |
| 2 | 2 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 5 | |
| C51 = 5 | 3 | 3 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 5 |
| 4 | 4 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 6 | |
| 5 | 5 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 5 | |
| 6 | 1+2 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 9 | |
| 7 | 1+3 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 7 | |
| 8 | 1+4 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 6 | |
| 9 | 1+5 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 5 | |
| C52 = 10 | 10 | 2+3 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 8 |
| 11 | 2+4 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 7 | |
| 12 | 2+5 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 6 | |
| 13 | 3+4 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 5 | |
| 14 | 3+5 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 6 | |
| 15 | 4+5 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 5 | |
| 16 | 1+2+3 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 8 | |
| 17 | 1+2+4 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 5 | |
| 18 | 1+2+5 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 8 | |
| 19 | 1+3+4 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 9 | |
| C53 = 10 | 20 | 1+3+5 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 10 |
| 21 | 1+4+5 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 7 | |
| 22 | 2+3+4 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 8 | |
| 23 | 2+3+5 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 5 | |
| 24 | 2+4+5 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 6 | |
| 25 | 3+4+5 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 8 | |
| 26 | 1+2+3+4 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 10 | |
| 27 | 1+2+3+5 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 11 | |
| C54 = 5 | 28 | 1+2+4+5 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 10 |
| 29 | 1+3+4+5 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 6 | |
| 30 | 2+3+4+5 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 11 | |
| C55 = 1 | 31 | 1+2+3+4+5 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 11 |
| 4.4. Определение доли необнаруженных ошибок. |
| Кратность ошибок | Число вариантов Cni | Числоbi | Доля необнаруженныхошибок | |
| bi / Cni | 1/2n-k | |||
| 1 | C151 = 15 | - | 0 | 9,76*10-4 |
| 2 | C152 = 105 | - | 0 | 9,76*10-4 |
| 3 | C153 = 455 | - | 0 | 9,76*10-4 |
| 4 | C154 = 1365 | - | 0 | 9,76*10-4 |
| 5 | C155 = 3003 | 8 | 2,66*10-3 | 9,76*10-4 |
| 6 | C156 = 5005 | 7 | 1,39*10-3 | 9,76*10-4 |
| 7 | C157 = 6435 | 3 | 4,66*10-4 | 9,76*10-4 |
| 8 | C158 = 6435 | 5 | 7,77*10-4 | 9,76*10-4 |
| 9 | C159 = 5005 | 2 | 3,996*10-5 | 9,76*10-4 |
| 10 | C1510 = 3003 | 3 | 9,99*10-4 | 9,76*10-4 |
| 11 | C1511 = 1365 | 3 | 2,19*10-3 | 9,76*10-4 |
| 12 | C1512 = 455 | - | 0 | 9,76*10-4 |
| 13 | C1513 = 105 | - | 0 | 9,76*10-4 |
| 14 | C1514 = 15 | - | 0 | 9,76*10-4 |
| 15 | C1515 = 1 | - | 0 | 9,76*10-4 |
Доля необнаруженных ошибок