Экстремальные коды

История применения кодов. Технология применения кодов в современных условиях. Анализ "экстремальных кодов" - кодов, границы параметров которых достигают равенства. Способность кода корректировать ошибки, ее зависимость от величины кодового расстояния.

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 14.07.2012
Размер файла 164,9 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Московский Институт Радиотехники, Электроники и Автоматики

(Технический университет)

Контрольная работа

по дисциплине

"Теория кодирования и информации"

на тему: "Экстремальные коды"

Выполнила: студентка гр. ВИ-1-07

Терёхина Юлия

Москва 2010

Содержание

  • Введение
  • Границы для параметров кодов
  • Заключение
  • Список используемой литературы

Введение

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

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

Способность кода корректировать ошибки находится в прямой зависимости от величины кодового расстояния - хорошие корректирующие свойства обеспечиваются большим кодовым расстоянием и наоборот. Для построения кодов с большим кодовым расстоянием требуется вводить много проверочных символов, не передающих информацию от источника к адресату, а выполняющих вспомогательную роль. Наличие большого числа проверочных символов при фиксированной длине кодового слова уменьшает число информационных символов, а следовательно, и скорость передачи информации Таким образом, хорошие корректирующие свойства кода и высокая скорость передачи информации - требования противоречивые. Поэтому задача построения кодов с приемлемыми значениями d и R - задача оптимизации, не имеющая единственного решения. Параметры n,k,d, характеризующие код, не могут принимать произвольных значений. Нетрудно видеть, что:

среди кодов с одинаковыми параметрами n и k лучшим является код, который имеет больше кодовое расстояние d,

среди кодов с одинаковыми параметрами n и d лучшим является код, который имеет большее число информационных символов k,

среди кодов с одинаковыми параметрами k и d лучшим является код, который имеет меньшую длину n, а следовательно, и меньшее число проверочных символов.

Между рассмотренными параметрами n,k,d существуют определённые соотношения, задаваемые границами для кодового расстояния

или для скорости передачи информации. Различают верхние и нижние границы;

k - длина вектора, который кодируем

d - кодовое расстояние.

n - длина закодированного вектора.

- скорость передачи информации кода.

1) Если фиксированы n, k, то

2) Если фиксированы n, d, то

3) Если фиксированы 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

подставляем:

получим верное равенство:

8=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 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, состоящий из двух

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

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

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

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

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

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

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

G =

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

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

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

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

H2 = =

H4 =

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

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

(n, k) - код (линейный) с минимальным кодовым расстоянием d, параметры которого удовлетворяют неравенству:

.

-

вероятность получить не более (d-2) успехов в схеме Бернулли.

Граница Варшамова - Гильберта является границей существования и дает нижнюю оценку кодового расстояния для "наилучшего" кода.

Теорема 4. (Оценка Чернова для биномиальных коэффициентов).

Пусть , то справедливо:

Из этих неравенств следует:

1) , d = 2t + 1

2) - следует из гр. Плоткина в случае лин. кода

3) - из гр. Варшамова-Гилберта

Заключение

Применение кодов

Первым кодом, исправляющим ошибки, который стал применяться в вычислительных машинах, был разработанный еще на заре теории кодирования в 1950 г. код Хэмминга. Этот код был разработан специально для применения в вычислительных машинах. Код Хэмминга стал применяться в вычислительных машинах не сразу, и это объясняется тем, что после появления кода Хэмминга постоянно совершенствовались сами запоминающие элементы; сначала использовались электронные лампы, далее появились параметроны, полупроводниковые элементы и наконец интегральные схемы. При этом надежность запоминающих элементов постоянно и быстро росла. Первой вычислительной машиной, в которой использовался код Хэмминга, была вычислительная машина IBM 7030, а в Японии - машина DIPS фирмы Japan Telephone and Telegraph Public. Однако если первая была построена спустя 10 лет после появления кода Хэмминга, то вторая - спустя 20 лет. До этого времени в вычислительных машинах использовался лишь простейший способ повышения надежности, а именно проверка на четность (или нечетность)

Код кратных повторений, который является эквидистантным кодом, предназначен для кодирования двоичной информации. Он обладает большой помехозащищенностью, но очень малой скоростью передачи информации.

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

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

экстремальный код равенство параметр

Список используемой литературы

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

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

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

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


Подобные документы

  • Изучение сущности циклических кодов - семейства помехоустойчивых кодов, включающих в себя одну из разновидностей кодов Хэмминга. Основные понятия и определения. Методы построения порождающей матрицы циклического кода. Понятие открытой системы. Модель OSI.

    контрольная работа [99,5 K], добавлен 25.01.2011

  • Обеспечение достоверности передаваемой информации применением корректирующих кодов. Код Хэмминга - алгоритм обнаружения и исправления одиночной ошибки. Использование циклических кодов при последовательной передачей между ЭВМ и внешними устройствами.

    дипломная работа [123,7 K], добавлен 02.08.2009

  • Циклические коды как подкласс (подмножество) линейных кодов, пошаговый алгоритм и варианты их кодирования и декодирования. Методика построения интерфейса отладочного модуля. Элементарный план и элементы отладки декодирующего модуля циклических кодов.

    лабораторная работа [133,8 K], добавлен 06.07.2009

  • Коды Боуза-Чоудхури-Хоквингема (БЧХ) – класс циклических кодов, исправляющих многократные ошибки. Отличие методики построения кодов БЧХ от обычных циклических. Конкретные примеры процедуры кодирования, декодирования, обнаружения и исправления ошибок.

    реферат [158,2 K], добавлен 16.07.2009

  • Порядок и основные этапы построения двоичных неравномерных эффективных кодов с помощью методики Хаффмена. Сравнительная характеристика полученных кодов. Кодирование текста построенными кодами. Разработка марковских процедур для кодирования слов.

    лабораторная работа [520,7 K], добавлен 29.09.2011

  • Определение понятий кода, кодирования и декодирования, виды, правила и задачи кодирования. Применение теорем Шеннона в теории связи. Классификация, параметры и построение помехоустойчивых кодов. Методы передачи кодов. Пример построения кода Шеннона.

    курсовая работа [212,6 K], добавлен 25.02.2009

  • Запись кодов команд программы и констант в FlashROM, кодов исходных данных в EEPROM, требуемых значений установочных битов (Fuse Bits) и битов защиты (Lock Bits). Запись и чтение кодов при программировании, способы программирования в микроконтроллерах.

    контрольная работа [24,2 K], добавлен 22.08.2010

  • Генерация порождающего полинома для циклического кода. Преобразование порождающей матрицы в проверочную и обратно. Расчет кодового расстояния для линейного блокового кода. Генерация таблицы зависимости векторов ошибок от синдрома для двоичных кодов.

    доклад [12,6 K], добавлен 11.11.2010

  • Разработка алгоритма и программы кодирования и декодирования данных кодом Рида-Малера. Понятие избыточных кодов, их применение. Корелляционный код. Особенности построения простых помехоустойчивых кодов Рида-Маллера. Рассмотрение частных случаев.

    курсовая работа [31,9 K], добавлен 09.03.2009

  • Создание базы из основной таблицы с оперативными данными и четырех таблиц справочников с наименованиями кодов. Расшифровка кодов в формах, в представлениях, в запросах и в отчетах. Логическая модель базы данных. Конструктор базового представления.

    курсовая работа [1,6 M], добавлен 08.04.2014

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.