Экстремальные коды
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
Московский Институт Радиотехники, Электроники и Автоматики
(Технический университет)
Контрольная работа
по дисциплине
"Теория кодирования и информации"
на тему: "Экстремальные коды"
Выполнила: студентка гр. ВИ-1-07
Терёхина Юлия
Москва 2010
Содержание
Введение
Границы для параметров кодов
Заключение
Список используемой литературы
Введение
Целью моей работы, является рассмотрение так называемых "экстремальных кодов", то есть коды, границы параметров которых достигают равенства.
Границы для параметров кодов
Способность кода корректировать ошибки находится в прямой зависимости от величины кодового расстояния - хорошие корректирующие свойства обеспечиваются большим кодовым расстоянием и наоборот. Для построения кодов с большим кодовым расстоянием требуется вводить много проверочных символов, не передающих информацию от источника к адресату, а выполняющих вспомогательную роль. Наличие большого числа проверочных символов при фиксированной длине кодового слова уменьшает число информационных символов, а следовательно, и скорость передачи информации Таким образом, хорошие корректирующие свойства кода и высокая скорость передачи информации - требования противоречивые. Поэтому задача построения кодов с приемлемыми значениями d и R - задача оптимизации, не имеющая единственного решения. Параметры n,k,d, характеризующие код, не могут принимать произвольных значений. Нетрудно видеть, что:
среди кодов с одинаковыми параметрами n и k лучшим является код, который имеет больше кодовое расстояние d,
среди кодов с одинаковыми параметрами n и d лучшим является код, который имеет большее число информационных символов k,
среди кодов с одинаковыми параметрами k и d лучшим является код, который имеет меньшую длину n, а следовательно, и меньшее число проверочных символов.
Между рассмотренными параметрами n,k,d существуют определённые соотношения, задаваемые границами для кодового расстояния
или для скорости передачи информации. Различают верхние и нижние границы;
k - длина вектора, который кодируем
d - кодовое расстояние.
n - длина закодированного вектора.
- скорость передачи информации кода.
) Если фиксированы n, k, то
) Если фиксированы n, d, то
) Если фиксированы k, d, то
Теорема 1. (Верхняя граница Хемминга)
.
Если существует линейный q-ичный код G с параметрами (n, k) и с кодовым расстоянием d = 2t + 1, то справедливо:
- оценка для d
Док-во: для рассмотрим множество:
,
Следствие:
- верхняя граница для d и для R
Возможна такая ситуация:
Равенство имеет место только для совершенных двоичных кодов.
Совершенный код обладает замечательным свойством: шары радиуса t с центрами в кодовых точках совершенного кода не пересекаются и одновременно заполняют всё пространство Vn.
Определение. Код, для которого справедливо:
,
называется совершенным (или плотноупакованным). Например, код кратных повторений, двоичный код Хемминга (7,4)
Двоичный код с повторениями при нечетной блоковой длине n исправляет вплоть до (n - 1) /2 ошибок. Для t = (n - 1) /2 и R = 1/n имеем
Таким образом, двоичный код с повторениями и нечетной блоковой длиной является совершенным, все другие совершенные коды должны иметь либо большую скорость передачи, либо малую блоковую длину. (*) описывает класс совершенных кодов с большой скоростью и малой корректирующей способностью (t = 1)
(*): В метрике Хемминга совершенный систематический код с исправлением одной ошибки и блоковой длиной n над алфавитом из q существует тогда и только тогда когда n =
Совершенные коды
Коды плотноупакованные - коды, которые имеют число синдромов, точно равное их необходимому числу, позволяют исправить все однократные ошибки в любом информативном и проверочном символах и включают один нулевой синдром.
.">К совершенным кодам относятся, например, коды Хемминга .
Коды Хэмминга
Кодом Хэмминга называется (n,k) - код, проверочная матрица которого имеет r = n-k строк и 2r-1 столбцов, причем столбцами являются все различные ненулевые последовательности.
Пример. Для (7,4) - кода Хэмминга
Двоичный код Хемминга (7,4)
n = 7 k = 4
подставляем:
получим верное рав?/p>