5. - Скорость кода (коэффициент кода)

Граничные соотношения между характеристиками помехоустойчивого кода.

I. Граница Хемминга.

Сколько в этой зоне запрещенных + 1 кодовых комбинаций?

Разделим на и прологарифмируем:

Граница Хемминга(граница плотной упаковки сферы)

Коды на границе Хемминга и есть сами коды Хемминга.

II. Граница Варшамова – Гилберта

Разделим на и прологарефмируем:

упрощенное выражение для границы Варшавова - Гилберта

Таких кодов значительно больше, чем кодов, удовлетворяющих границы Хемминга, и эти коды хорошие.

III. Граница максимально разнесенных кодов (максимальная граница)

Устанавливает максимальное значение для определенной избыточности.

Таких кодов мало: коды с проверкой на четность и другие. Ее открыл Синглтон (граница Синглтона).

Классификация помехоустойчивых кодов.

Групповые коды.

Определение группы и её свойства.

Блоковые коды – характеризуются длиной кодовой комбинации n (n-последовательность).

Действия над кодовыми комбинациями – поразрядное сложение (по mod2)/

Группа – одна из основных систем, рассматриваемых в высшей математике.

Группой (G) называется множество элементов произвольной природы, для которых задано одно из действий (либо сложение, либо умножение). И по этому действию (операции) это множество обладает следующими свойствами (удовлетворяют следующим аксиомам):

1. Замкнутость.

Рассмотрим на примере сложения (для умножения тоже самое).

2. Ассоциативность (сочетательность).

3. Наличие единичного элемента.

Среди элементов группы есть единственный элемент l, такой что для любого элемента группы a выполняется соотношение:

Например,

4. Наличие обратных элементов.

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

5. Коммутативность.

Если a и b элементы группы и не важен порядок, т.е. то такая группа называется коммутативной или абелевой.

Группа называется конечной, если она состоит из конечного числа элементов. В противном случае она называется бесконечной.

Пример.

Задав в качестве групповой операции операцию сложения по mod2, убедимся, что множество 000, 001, 010, 100, 110, 011, 101, 111 является группой. Складывая элементы множества в различном сочетании, видим, что каждый раз получаем элемент, входящий в множество. Так, и т.п. Легко заметить, что условие ассоциативности также выполняется. Единичным является элемент 000. Для каждого элемента, заданного в примере множества, существует обратный. Так, для элемента 100 обратным является он сам, т.е.. Таким образом, рассматриваемое множество является группой, порядок которой (число элементов) равен восьми. Видно также, что данная группа является коммутативной.

Групповым кодом называется множество n-последовательностей, которые являются абелевой группой по введённой операции поразрядного сложения .

Для групповых кодов принято обозначение (n,k) – код (k – число информационных элементов, n – общее число элементов).

Свойства групповых кодов.

1. Групповой (линейный) код является подгруппой множества всех последовательностей длины n. (А множество всех последовательностей длины n называется группой).

Для того, чтобы множество из n-последовательности из общего числа всех последовательностей длины n было группой, достаточно проверить наличие единичного элемента (нулевого) и замкнутость.

2. Min кодовое расстояние группового кода равно весу его ненулевых комбинаций.

Это свойство обусловлено тем, что сумма любых комбинаций группового кода также является кодовой комбинацией, а значит комбинация min веса указывает на степень удалённости комбинаций данного кода.

Любой групповой код не обнаруживает только те ошибки, которые по своему виду совпадают с видом кодовой комбинации.

Способы задания групповых кодов.

a₀, a₁, a₂, a₃, … a_n-1 – последовательность длины n.

- вектор n-мерного пространства (- скаляр,- орт).

N_П ~ V_П

N_К ~ V_К

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

2. Линейная комбинация кодовой комбинации.

3. Линейная зависимость и линейная независимость. (Линейная независимость: W = 0, когда все с_i = 0)

Способы задания.

1. По аналогии с линейным векторным пространством можно задавать групповые коды с помощью базиса подпространства размерности k n-мерного векторного пространства. [Порождающая матрица кода (ПМК)]

Строками этой таблицы являются k линейно независимых кодовых комбинаций.

ПМК обозначается: (), , [].

Пример.

Пусть в групповом (5,3) коде связи между информационными и избыточными элементами задаются с помощью следующих линейных отношений:

Элементы комбинаций кода a₀, a₁, a₂, a₃, a₄, где a₂, a₃, a₄ - информационные, а a₀, a₁ – избыточные элементы. Избыточные элементы могут быть получены путём суммирования по mod2 определённых информационных элементов. Т.о. ,.

00 000

10 100

11 010

01 110

01 001

11 101

10 011

00 111

Первые два столбца – это избыточные элементы, полученные путём суммирования по mod2 определённых информационных элементов, а оставшиеся три столбца – информационные элементы. Исходя из этого можно построить ПМК:

R

I

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

n

2. Проверочная матрица группового кода (Н).

Свойство.

Если два вектора по скалярному произведению равны нулю, то они ортогональны.

Смотри предыдущий пример.

a₀, a₁, a₂, a₃, a₄

Проверочные вектора

R`

- базис нулевого пространства (5,3) кода.

H – базис нулевого пространства (n,k) кода.

в качестве строк – проверочные вектора данного кода.

n-k

n-k

k , k–транспонированная проверочная матрица.

Проверочная матрица группового кода как и ПМК может быть записана в канонической форме:

Т.о. проверочная матрица как и ПМК служит для краткого задания кода. Она задаёт код через проверочные соотношения, существующие для данного кода. Используя связь между канонической формой ПМК и проверочной матрицей мы легко по одной из них находим другую.