овані k , d , то
Теорема 1. (Верхня межа Хеммінга)
У теорії кодування <# "58" src = "doc_zip6.jpg"/> - оцінка для d
Док-во: для розглянемо безліч:
В В В В
,
Слідство:
- верхня межа для d і для R
Можлива така ситуація:
В
Рівність має місце тільки для досконалих двійкових кодів.
Досконалий код має чудову властивість: кулі радіуса t з центрами в кодових точках досконалого коду не перетинаються і одночасно заповнюють весь простір V n.
Визначення. Код, для якого справедливо:
,
називається досконалим (або щільноупакована). Наприклад, код кратних повторень, двійковий код Хемінга (7,4)
Двійковий код з повтореннями при непарній блокової довжині n виправляє аж до (n - 1)/2 помилок. Для t = (n - 1)/2 і R = 1/n маємо
В
Таким чином, двійковий код з повтореннями і непарної блокової довжиною є досконалим, всі інші вчинені коди повинні мати або велику швидкість передачі, або малу блокову довжину. (*) Описує клас досконалих кодів з великою швидкістю і малою коректує здатністю (t = 1)
(*): У метриці Хемінга досконалий систематичний код з виправленням однієї помилки і блокової довжиною n над алфавітом із q існує тоді і тільки тоді коли n =
Досконалі коди
Коди щільноупаковані - коди, які мають число синдромів, точно рівне їх необхідному числу, дозволяють виправити всі однократні помилки в будь-якому інформативному і перевірочному символах і включають один нульовий синдром.
До досконалим кодами відносяться, наприклад, коди Хеммінга <# "23" src = "doc_zip22.jpg"/>
отримаємо вірне рівність:
= 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 () у двійковій за...
