АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Важнейшие линейные коды

Читайте также:
  1. II. Важнейшие свидетсли новозаветного текста
  2. Важнейшие антропологические открытия XIX – XX веков.
  3. Важнейшие археологические открытия в Южной Корее начала XXI в.
  4. ВАЖНЕЙШИЕ ВИДЫ ЧАСТНЫХ ДЕЛИКТОВ
  5. Важнейшие механизмы творческой деятельности
  6. Важнейшие направления и проблемы изучения античной истории. Наследие Древней Греции и Древнего Рима в современном мире.
  7. Важнейшие отличия заболеваний, сопровождающихся болями в ухе
  8. Важнейшие работы по текстологии, не упомянутые в тексте книги
  9. Важнейшие элементы культуры
  10. Глава 2. Линейные оптимизационные задачи и методы их решения.
  11. Диеновые углеводороды (алкадиены): особенности химических свойств сопряженных диенов. Важнейшие представители. Получение и применение в промышленности.

Код Хэмминга – является одним из важнейших линейных кодов. Коды Хэмминга имеют параметры (2m - 1; 2m - 1 - m) и обычно задаются проверочной матрицей. Столбцами проверочной матрицы являются все ненулевые двоичные числа длины m. Например, для кода (7, 4) проверочная матрица имеет следующий вид:

0 0 0 1 1 1 1

H = 0 1 1 0 0 1 1

1 0 1 0 1 0 1

Столбцы с номерами 1, 2, 4, образующие единичную подматрицу, являются проверочными.

Определим корректирующую способность кодов Хэмминга. Предварительно напомним, что весом W(a) слова а называется число ненулевых элементов, и в линейном коде расстояние d(a, b) между двумя словами а и b равно весу некоторого третьего слова а + b, то есть d(a, b) = W(a + b).

Для определения минимального расстояния воспользуемся равенством a. HT = 0.

Предположим, что d(a, b) = 1 . Тогда в коде существует слово веса 1, что невозможно, так как для слов веса один, a. HT ≠ 0. Теперь предположим, что d(a, b) = 2. Тогда в коде существует слово веса 2, что также невозможно, поскольку никакие два столбца проверочной матрицы не дадут в сумме нулевой вектор. Следовательно, d(a, b) >= 3.

Простым подбором нетрудно найти слово веса три, для которого a. HT = 0 Окончательно получим dmin = 3, то есть коды Хэмминга исправляют любую одиночную ошибку. Поскольку все 2m - 1 векторов, задающих одиночные ошибки, принадлежат различным смежным классам, то этими смежными классами и кодовым пространством исчерпываются все 2m смежных классов. Их образующими является ненулевой вектор и векторы единичного веса. Следовательно, коды Хэмминга являются совершенными.

Код Хэмминга можно удлинить на один символ, добавив общую проверку на четность. Добавление проверочного символа увеличивает вес слов на единицу, то есть d = 4. Проверочная матрица Н" удлиненного кода имеет вид:

H = 0 H

: :

1 1 1 0 . . . 1

 

 

Декодирование производится так:

1.Если синдром равен нулю, то считается, что ошибок нет.

2.Если синдром отличен от нуля и на последнем месте стоит 1, то предполагается, что произошла одиночная ошибка, на местоположение которой указывает синдром матрицы Н.

3.Если синдром отличен от нуля и на последнем месте стоит 0, то обнаружена неисправимая ошибка.

 

На практике чаще используются модифицированные (укороченные) коды Хэмминга. Операция укорочения является обратной к только что описанной операции удлинения и заключается в выборе всех кодовых слов, первая координата которых равна нулю, X1 = 0, и в удалении этой координаты в выбранных словах. Размерность данных кодов (2m - 2; 2m - m - 2).Укорочение кодов используется для упрощения схем кодеков.

 

...

1 | 2 | 3 | 4 | 5 |



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)