Помехоустойчивое кодирование код хемминга

Помехоустойчивое кодирование код хемминга

Код — это набор условных обозначений (или сигналов) для записи (или передачи) некоторых заранее определенных понятий.

Кодирование информации – это процесс формирования определенного представления информации. В более узком смысле под термином «кодирование» часто понимают переход от одной формы представления информации к другой, более удобной для хранения, передачи или обработки.

Обычно каждый образ при кодировании (иногда говорят — шифровке) представлен отдельным знаком.

Знак — это элемент конечного множества отличных друг от друга элементов.

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

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

Одна и та же информация может быть представлена (закодирована) в нескольких формах. C появлением компьютеров возникла необходимость кодирования всех видов информации, с которыми имеет дело и отдельный человек, и человечество в целом. Но решать задачу кодирования информации человечество начало задолго до появления компьютеров. Грандиозные достижения человечества — письменность и арифметика — есть не что иное, как система кодирования речи и числовой информации. Информация никогда не появляется в чистом виде, она всегда как-то представлена, как-то закодирована.

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

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

Кодирование Хэмминга предусматривает как возможность обнаружения ошибки, так и возможность её исправления. Рассмотрим простой пример — закодируем четыре бита: a,b,c,d.Полученный код будет иметь длину 8 бит и выглядеть следующим образом: Рассмотрим табличную визуализацию кода:

Как видно из таблицы, даже если один из битов передался с ошибкой, содержащие его -суммы не сойдутся. Итого, зная строку и столбец в проиллюстрированной таблице можно точно исправить ошибочный бит.

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

§ Первая пара: сумма четных бит и сумма нечетных бит

§ Вторая пара: сумма тех бит, в чьем номере второй бит с конца ноль и сумма тех бит, в чьем номере второй бит с конца единица

§ -тая пара: сумма тех бит, в чьем номере -тый бит с конца ноль и сумма тех бит, в чьем номере -тый бит с конца единица.

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

Теперь заметим, что в случае наличия ошибки в исходной строке, ровно один бит в каждой паре будет равен единице. Тогда можно оставить только один бит из пары. Однако этого будет недостаточно, поскольку если только один добавленный бит не соответствует строке, то нельзя понять, ошибка в нём или в строке. На этот случай можно добавить ещё один контрольный бит — всех битов строки.

Читайте также:  На флешке появился ярлык самой флешки

Итого, увеличивая код длиной на , можно обнаружить и исправить одну ошибку.

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

Алгоритм Хаффмана — адаптивный простой алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.

В отличие от алгоритма Шеннона — Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов m2 с более чем двумя символами.

Этот метод кодирования состоит из двух основных этапов:

· Построение оптимального кодового дерева.

· Построение отображения код-символ на основе построенного дерева.

Код Хэмминга относится к классу линейных кодов и представляет собой систематический код – код, в котором информационные и контрольные биты расположены на строго определенных местах в кодовой комбинации.

Код Хэмминга, как и любой (n, k)- код, содержит к информационных и m = n-k избыточных (проверочных) бит.

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

Существуют различные методы реализации кода Хэмминга и кодов которые являются модификацией кода Хэмминга. Рассмотрим алгоритм построения кода для исправления одиночной ошибки.

1. По заданному количеству информационных символов — k, либо информационных комбинаций N = 2 k , используя соотношения:

вычисляют основные параметры кода n и m.

2. Определяем рабочие и контрольные позиции кодовой комбинации. Номера контрольных позиций определяются по закону 2 i , где i=1, 2, 3. т.е. они равны 1, 2, 4, 8, 16,… а остальные позиции являются рабочими.

3. Определяем значения контрольных разрядов (0 или 1 ) при помощи многократных проверок кодовой комбинации на четность. Количество проверок равно m = n-k. В каждую проверку включается один контро-льный и определенные проверочные биты. Если результат проверки дает четное число, то контрольному биту присваивается значение -0, в противном случае — 1. Номера информационных бит, включаемых в каждую проверку, определяются по двоичному коду натуральных n –чисел разрядностью – m (табл. 1, для m = 4) или при помощи проверочной матрицы H(mn), столбцы которой представляют запись в двоичной системе всех целых чисел от 1 до 2 k 1 перечисленных в возрастающем порядке. Для m = 3 проверочная матрица имеет вид

. (15 )

Количество разрядов m — определяет количество проверок.

В первую проверку включают коэффициенты, содержащие 1 в младшем (первом) разряде, т. е. b1, b3, b5 и т. д.

Во вторую проверку включают коэффициенты, содержащие 1 во втором разряде, т. е. b2, b3, b6 и т. д.

В третью проверку — коэффициенты которые содержат 1 в третьем разряде и т. д.

Двоичные числа и их разряды

Для обнаружения и исправления ошибки составляются аналогичные проверки на четность контрольных сумм, результатом которых является двоичное (n-k) -разрядное число, называемое синдромом и указывающим на положение ошибки, т. е. номер ошибочной позиции, который определяется по двоичной записи числа, либо по проверочной матрице.

Читайте также:  Как на айфоне отключить звук звонка

Для исправления ошибки необходимо проинвертировать бит в ошибочной позиции. Для исправления одиночной ошибки и обнаружения двойной используют дополнительную проверку на четность. Если при исправлении ошибки контроль на четность фиксирует ошибку, то значит в кодовой комбинации две ошибки.

Схема кодера и декодера для кода Хэмминга приведена на рис. 1.

Пример 1. Построить код Хемминга для передачи сообщений в виде последовательности десятичных цифр, представленных в виде 4 –х разрярных двоичных слов. Показать процесс кодирования, декодирования и исправления одиночной ошибки на примере информационного слова 0101.

1. По заданной длине информационного слова (k = 4), определим количество контрольных разрядов m, используя соотношение:

при этом n = k+m = 7, т. е. получили (7, 4) -код.

2. Определяем номера рабочих и контрольных позиции кодовой комбинации. Номера контрольных позиций выбираем по закону 2 i .

Для рассматриваемой задачи (при n = 7) номера контрольных позиций равны 1, 2, 4. При этом кодовая комбинация имеет вид:

3. Определяем значения контрольных разрядов (0 или 1), используя проверочную матрицу (5).

Передаваемая кодовая комбинация: 0 1 0 0 1 0 1

Допустим принято: 0 1 1 0 1 0 1

Для обнаружения и исправления ошибки составим аналогичные про-верки на четность контрольных сумм, в соответствии с проверочной матрицей результатом которых является двоичное (n-k) -разрядное число, называемое синдромом и указывающим на положение ошибки, т. е, номер ошибочной позиции.

Сравнивая синдром ошибки со столбцами проверочной матрицы, определяем номер ошибочного бита. Синдрому 011 соответствует третий столбец, т. е. ошибка в третьем разряде кодовой комбинации. Символ в 3 -й позиции необходимо изменить на обратный.

Пример 2. Построить код Хэмминга для передачи кодовой комбинации 1 1 0 1 1 0 1 1. Показать процесс обнаружения и исправления ошибки в соответствующем разряде кодовой комбинации.

Решение: Рассмотрим алгоритм построения кода для исправления одиночной ошибки.

1. По заданной длине информационного слова (k = 8) , используя соотношения вычислим основные параметры кода n и m.

при этом n = k+m = 12, т. е. получили (12, 8)-код.

2. Определяем номера рабочих и контрольных позиции кодовой комбинации. Номера контрольных позиций выбираем по закону 2 i .

Для рассматриваемой задачи (при n = 12) номера контрольных позиций равны 1, 4, 8.

При этом кодовая комбинация имеет вид:

3. Определяем значения контрольных разрядов (0 или 1) путем много-кратных проверок кодовой комбинации на четность. Количество проверок равно m = n-k. В каждую проверку включается один контрольный и определенные проверочные биты.

Номера информационных бит, включаемых в каждую проверку определяется по двоичному коду натуральных n-чисел разрядностью — m.

0001 b1 Количество разрядов m — определяет количество прове-

Передаваемая кодовая комбинация: 1 2 3 4 5 6 7 8 9 10 11 12

1 1 1 1 1 0 1 1 1 0 1 1

Допустим, принято: 1 1 1 1 0 0 1 1 1 0 1 1

Для обнаружения и исправления ошибки составим аналогичные про-верки на четность контрольных сумм, результатом которых является двоичное (n-k) -разрядное число, называемое синдромом и указывающим на положение ошибки, т. е. номер ошибочной позиции.

Обнаружена ошибка в разряде кодовой комбинации с номером 0101, т. е. в 5 -м разряде. Для исправления ошибки необходимо проинвертировать 5 -й разряд в кодовой комбинации.

Рис. 1. Схема кодера —а и декодера –б для простого (7, 4) кода Хэмминга

Рассмотрим применение кода Хэмминга. В ЭВМ код Хэмминга чаще всего используется для обнаружения и исправления ошибок в ОП, памяти с обнаружением и исправлением ошибок ECC Memory (Error Checking and Correcting). Код Хэмминга используется как при параллельной, так и при последовательной записи. В ЭВМ значительная часть интенсивности потока ошибок приходится на ОП. Причинами постоянных неисправностей являются отказы ИС, а случайных изменение содержимого ОП за счет флуктуации питающего напряжения, кратковременных помех и излучений. Неисправность может быть в одном бите, линии выборки разряда, слова либо всей ИС. Сбой может возникнуть при формировании кода (параллельного), адреса или данных, поэтому защищать необходимо и то и др. Обычно дешифратор адреса встроен в м/схему и недоступен для потребителя. Наиболее часто ошибки дают ячейки памяти ЗУ, поэтому главным образом защищают записываемые и считываемые данные.

Читайте также:  Двойные часы на рабочий стол

Наибольшее применение в ЗУ нашли коды Хэмминга с dmin=4, исправляющие одиночные ошибки и обнаруживающие двойные.

Проверочные символы записываются либо в основное, либо специальное ЗУ. Для каждого записываемого информационного слова (а не байта, как при контроле по паритету) по определенным правилам вычисляется функция свертки, результат которой разрядностью в несколько бит также записывается в память. Для 16 -ти разрядного информационного слова используется 6 дополнительных бит (32- 7 бит, 64 –8 бит). При считывании информации схема контроля, используя избыточные биты, позволяет обнаружить ошибки различной кратности или исправить одиночную ошибку. Возможны различные варианты поведения системы:

автоматическое исправление ошибки без уведомления системы;

— исправление однократной ошибки и уведомление системы только о многократных ошибках;

— не исправление ошибки, а только уведомление системы об ошибках;

Модуль памяти со встроенной схемой исправления ошибок –EOS 72/64 (ECC on Simm). Аналог микросхема к 555 вж 1 -это 16 разрядная схема с обнаружением и исправлением ошибок (ОИО) по коду Хэмминга (22, 16), использование которой позволяет исправить однократные ошибки и обнаружить все двух кратные ошибки в ЗУ.

Избыточные (контрольные) разряды позволяют обнаружить и исправить ошибки в ЗУ в процессе записи и хранения информации.

В составе ВЖ-1 используются 16 информационных и 6 контрольных разрядов. (DB — информационное слово, CB — контрольное слово).

При записи осуществляется формирование кода, состоящего из 16 информационных и 6 контрольных разрядов, представляющих результат суммирование по модулю 2 восьми информационных разрядов в соответствии с кодом Хэмминга. Сформированные контрольные разряды вместе с информационными поступают на схему и записываются в ЗУ.

Рис.2. Схема контроля

При считывании шестнадцатиразрядное слово декодируется, восстанавливаясь вместе с 6 разрядным словом контрольным, поступают на схему сравнения и контроля. Если достигнуто равенство всех контрольных разрядов и двоичных слов, то ошибки нет.

Любая однократная ошибка в 16 разрядном слове данных изменяет 3 байта в 6 разрядном контрольном слове. Обнаруженный ошибочный бит инвертируется.

Проблема повышения верности обусловлена не соответствием между требованиями, предъявляемыми при передачи данных и качеством реальных каналов связи. В сетях передачи данных требуется обеспечить верность не хуже 10 -6 — 10 -9 , а при использовании реальных каналов связи и простого (первичного) кода указанная верность не превышает 10 -2 — 10 -5 .

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

Простые коды характеризуются тем, что для передачи информации используются все кодовые слова (комбинации), количество которых равно N=q n (q — основание кода, а n — длина кода). В общем случае они могут отличаться друг от друга одним символом (элементом). Поэтому даже один ошибочно принятый символ приводит к замене одного кодового слова другим и, следовательно, к неправильному приему сообщения в целом.

Помехоустойчивыми называются коды, позволяющие обнаруживать и (или) исправлять ошибки в кодовых словах, которые возникают при передаче по каналам связи. Эти коды строятся таким образом, что для передачи сообщения используется лишь часть кодовых слов, которые отличаются друг от друга более чем в одном символе. Эти кодовые слова называются разрешенными. Все остальные кодовые слова не используются и относятся к числу запрещенных. Кодовое расстояние d(расстояние Хэмминга) между двумя кодовыми комбинациями – количество несовпадающих разрядов. d легко вычисляется, если две кодовые комбинации сложить по модулю два и посчитать количество единиц у результата сложения.

dmin – минимальное кодовое расстояние, которое равно минимальному кодовому расстоянию всех возможных комбинаций кода.

dmin определяет способность помехоустойчивого кода (ПУК) обнаруживать и исправлять ошибки: dmin≥r+1; dmin≥2s+1; dmin≥s+r+1 (если s i -1 .

Количество необходимых контрольных разрядов вычисляется следующим образом: 2 k ≥ m+k+1.

А число информационных разрядов зависит от количества букв Q в используемом алфавите: m = log2Q.

Ссылка на основную публикацию
Нет msvcr120 dll что делать
Если, попытавшись включить любимую игру, вы натыкаетесь на окно, которое гласит, что запуск программы невозможен по причине отсутствия mscvr120.dll —...
Консольные команды для бателфилд 4
Встречаем и вновь возвращаемся в самый: динамический, красивый, технически богатый и самый заселённый мир с постоянно ведущимися боевыми действиями. Самый...
Конструкция степлера канцелярского схема
Первые степлеры появились во Франции в XVIII веке, их специально изобрели для короля Людовика XV. Но в то время это...
Нет беспроводного сетевого соединения windows 7
На панели задач в Windows или в меню «Центр управление сетями» нет иконки Wi-Fi? Это не значит, что вышло из...
Adblock detector