Экстремальные коды
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
µнство:
=23 код является экстремальным
или
Проверочная матрица любого кода Хэмминга всегда содержит минимум три линейно зависимых столбца, поэтому кодовое расстояние кода равно трем.
Если столбцы проверочной матрицы представляют упорядоченную запись десятичных чисел, т.е.1,2,3. в двоичной форме, то вычисленный синдром однозначно указывает на номер позиции искаженного символа.
Определение. Двоичный код с длиной блока n = 2r-1, проверочной матрицей Hr (rxn), образованной всеми ненулевыми векторами из Vr (GF (2)), расположенными в порядке возрастания чисел, двоичные разложения которых совпадают с рассматриваемыми столбцами, называется двоичным кодом Хемминга.
Введённый (n = 2r - 1, k = 2r - 1 - r) - код будем обозначать Нr.
Рассмотрим процедуру декодирования для кодов Хемминга. Пусть произошла ошибка в i-м символе передаваемого кодового слова . Подсчитаем синдром полученного вектора: = + , где , = ( 0,…, 0)
S () = Hh-T = H ( + ) T = H= (1)
Следовательно, если произошла одна ошибка, то синдром S () в двоичной записи указывает номер столбца, в котором произошла ошибка. Соотношение (1) задаёт изящный и очень простой способ декодирования. Из свойств кода исправлять одну ошибку следует, что кодовое расстояние d 3. Заметим, что вектор (1110,.,0) принадлежит Нr, что проверяется умножением на проверочную матрицу.
Следовательно, d = 3.
Код Хэмминга используется в некоторых прикладных программах в области хранения данных; кроме того, метод Хемминга позволяет "на лету" исправлять однократные и обнаруживать двукратные ошибки.
При использовании совершенных кодов всегда возможна коррекция ошибок (не обязательно правильная). Помимо кодов Хэмминга, в настоящее время известно мало совершенных кодов.
Теорема 2. (Верхняя граница Плоткина)
Если существует q-ичный блоковый код с числом слов М и кодовым расстоянием d, то справедливо:
Определение. Когда это неравенство превращается в равенство, то код называется эквидистантным. Это возможно, когда расстояние между кодовыми словами одинаково и равно d.
Пример: , а также код кратных повторений.
Эквидистантные коды
Теорема. Каждое ненулевое кодовое слово циклического регистрового кода максимальной длины является циклическим сдвигом любого другого ненулевого кодового слова. Таким образом, в метрике Хэмминга все регистровые коды максимальной длины, являются эквидистантными.
Блочные эквидистантные коды с произвольным основанием q, в которых расстояние (Хэмминга) d строго достигает верхней границы, возможной при заданных q, числе кодовых слов M и длине кодового слова n. Такие коды именуются сокращенно EDm - кодами (q, M, n, d).
EDm - Коды интересны, в частности, по следующим причинам. Они составляют экстремальный класс q-ичных кодов. EDm - Коды можно использовать для построения других кодов с разными основаниями вплоть до q = 2.
Рассмотрим код с параметрами q, M, n, d. EDm - коды с dm и 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 1 1 1 1 1 1
1 1 1 0 0 0 1 1 1
0 1 1 0 1 1 0 0 1
1 0 1 1 0 1 0 1 0
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, состоящий из двух
кодовых слов 0 = (00000), 1= (11111). Этот код предназначен для
кодирования двоичной информации. Он обладает большой
помехозащищенностью, но очень малой скоростью передачи
информации. На один информационный - полезный символ в кодовом
слове приходится 4 проверочных символа. Введённый код
называется кодом кратных повторений.
Пусть q = 2, n = 5.
=
Очевидно, что код G - подпространство V5 (GF (2)). Ненулевое слово минимального веса - (00101). Кодовое расстояние кода G равно 2.
Другим простым примером является код ?2= { (000), (110), (101), (011) }. Если отметить вершины единичного куба, соответствующие кодовым словам кода ?2, и соединить их, то построенная фигура будет представлять симплекс. Это и даёт основание назвать код ?2 симплексным. Другими примерами эквивидистантных кодов являются коды, построенные с использованием матриц Адамара, коды, составленные из последовательностей максимальной длины.
Эквидистантные двоичные коды из K слов с блоковой длиной K-1 могут быть построены на основе ма