Целью моей работы, является рассмотрение так называемых "экстремальных кодов", то есть коды, границы параметров которых достигают равенства.

Границы для параметров кодов

В теории кодирования граница Хемминга определяет пределы возможных значений параметров произвольного блокового кода.

Если существует линейный q-ичный код G с параметрами (n, k) и с кодовым расстоянием d = 2t + 1, то справедливо:

- оценка для d

Док-во: для рассмотрим множество:

,

Следствие:

- верхняя граница для d и для R

Возможна такая ситуация:

Равенство имеет место только для совершенных двоичных кодов.

Совершенный код обладает замечательным свойством: шары радиуса t с центрами в кодовых точках совершенного кода не пересекаются и одновременно заполняют всё пространство V_n.

Определение. Код, для которого справедливо:

,

называется совершенным (или плотноупакованным). Например, код кратных повторений, двоичный код Хемминга (7,4)

Двоичный код с повторениями при нечетной блоковой длине n исправляет вплоть до (n - 1) /2 ошибок. Для t = (n - 1) /2 и R = 1/n имеем

Таким образом, двоичный код с повторениями и нечетной блоковой длиной является совершенным, все другие совершенные коды должны иметь либо большую скорость передачи, либо малую блоковую длину. (*) описывает класс совершенных кодов с большой скоростью и малой корректирующей способностью (t = 1)

(*): В метрике Хемминга совершенный систематический код с исправлением одной ошибки и блоковой длиной n над алфавитом из q существует тогда и только тогда когда n =

Совершенные коды

Если существует q-ичный блоковый код с числом слов М и кодовым расстоянием d, то справедливо:

Определение. Когда это неравенство превращается в равенство, то код называется эквидистантным. Это возможно, когда расстояние между кодовыми словами одинаково и равно d.

Пример: , а также код кратных повторений.

Эквидистантные коды

Теорема. Каждое ненулевое кодовое слово циклического регистрового кода максимальной длины является циклическим сдвигом любого другого ненулевого кодового слова. Таким образом, в метрике Хэмминга все регистровые коды максимальной длины, являются эквидистантными.

Блочные эквидистантные коды с произвольным основанием q, в которых расстояние (Хэмминга) d строго достигает верхней границы, возможной при заданных q, числе кодовых слов M и длине кодового слова n. Такие коды именуются сокращенно EDm - кодами (q, M, n, d).

EDm - Коды интересны, в частности, по следующим причинам. Они составляют экстремальный класс q-ичных кодов. EDm - Коды можно использовать для построения других кодов с разными основаниями вплоть до q = 2.

Рассмотрим код с параметрами q, M, n, d. EDm - коды с d_m и M= qt следующим образом:

Для достижения целочисленности _m:

так как = nM (q-l) / (M-l) q = nt (q - 1) / (qt - 1) (*),

то n = c (qt - 1) / (q - 1, t - 1), где с 1 - целое.

В EDm - кодах расстояние точно достигает (*), любой

из q символов повторяется в каждом столбце точно t раз, t 1, и параметры имеют вид:

M = qt, n, d = nt (q - 1) / (qt - 1).

Из соотношений получаем, что параметры EDm - кодов всегда могут быть представлены в виде:

M = qt, n = c (qt - 1) / (q - 1, t - 1), d = ct (q - 1) / (q - 1, t - 1).

Тривиальным случаем является код с t = 1 с произвольным n и d = n.

Здесь каждое из q слов содержит n-кратное повторение одного из q символов.

Отметим, что имеются значения параметров t и q, для которых EDm-код при с = 1 не существует, но существует при некотором с > 1. Например,

при t = 3, q = 2 код с параметрами M = 6, n= 5, d = 3, соответствующий

значению с = 1, не существует.

Однако имеется EDm - код с с = 2 и параметрами M = 6, n = 10, d = 6

0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 1 1 1 1 1

0 1 1 1 0 0 0 1 1 1

1 0 1 1 0 1 1 0 0 1

1 1 0 1 1 0 1 0 1 0

1 1 1 0 1 1 0 1 0 0

Подставим эти параметры в

Получим верное равенство 6=6 код с таким параметрами является эквидистантным.

Тривиальным примером эквидистантного кода является код [n,1,n] _{Щ -} код с повторениями (или код констант).

Код с повторениями (или код констант)

Пусть Щ - произвольное конечное множество. Код K = { (a,…,a): a ЎКЩ} есть [n,1,n] _{Щ -} код.

Пример. Пусть q = 2, n = 5. Рассмотрим код G, состоящий из двух

кодовых слов ₀ = (00000), ₁= (11111). Этот код предназначен для

кодирования двоичной информации. Он обладает большой

помехозащищенностью, но очень малой скоростью передачи

информации. На один информационный - полезный символ в кодовом

слове приходится 4 проверочных символа. Введённый код

называется кодом кратных повторений.

Пусть q = 2, n = 5.

G =

Очевидно, что код G - подпространство V₅ (GF (2)). Ненулевое слово минимального веса - (00101). Кодовое расстояние кода G равно 2.

Другим простым примером является код ¦І₂= { (000), (110), (101), (011) }. Если отметить вершины единичного куба, соответствующие кодовым словам кода ¦І_2, и соединить их, то построенная фигура будет представлять симплекс. Это и даёт основание назвать код ¦І₂ симплексным. Другими примерами эквивидистантных кодов являются коды, построенные с использованием матриц Адамара, коды, составленные из последовательностей максимальной длины.

Эквидистантные двоичные коды из K слов с блоковой длиной K-1 могут быть построены на основе матрицы Адамара.

Матрицей Адамара называется ортогональная (KK) - матрица, элементами которой являются числа +1 и - 1. Например:

H₂ = =

H₄ =

Без потери общности можно предположить, что все элементы первой строки и первого столбца матрицы Адамара равны +1. Отбрасывая первый столбец (KK) - матрицы Адамара, получим K строк длины K-1, образующих двоичный эквидистантный код. Если K не есть степень числа 2, то получается нелинейный код.

Теорема 3. (Нижняя граница Варшамова - Гилберта).

1. А. А. Духин "Теория информации", Москва, Гелиос АРВ, 2007 г.

2. Касами Т. "Теория кодирования" издательство "мир", Москва, 1978 г.

3. Н.В. Семаков, В.А. Зиновьев "Эквидистантные q-ичные коды с максимальным расстоянием и разрешимые уравновешенные блок-схемы" (1967 г.)

Размещено на Allbest.ru