Максимальная кратность обнаруживаемой ошибки - Ремонт и установка крупной бытовой техники

Число обнаруживаемых или исправляемых ошибок.

При применении двоичных кодов учитывают
только дискретные искажения, при которых
единица переходит в нуль (1 → 0) или нуль
переходит в единицу (0 → 1). Переход 1 →
0 или 0 → 1 только в одном элементе кодовой
комбинации называют единичной ошибкой
(единичным искажением). В общем случае
под кратностью ошибки подразумевают
число позиций кодовой комбинации, на
которых под действием помехи одни
символы оказались заменёнными на другие.
Возможны двукратные (t= 2) и многократные (t> 2) искажения элементов в кодовой
комбинации в пределах 0 <t<n.

Минимальное кодовое расстояние является
основным параметром, характеризующим
корректирующие способности данного
кода. Если код используется только для
обнаружения ошибок кратностью t₀,
то необходимо и достаточно, чтобы
минимальное кодовое расстояние было
равно

d_min
> t₀
+ 1. (13.10)

В этом случае никакая комбинация из t₀ошибок не может перевести одну разрешённую
кодовую комбинацию в другую разрешённую.
Таким образом, условие обнаружения всех
ошибок кратностьюt₀можно записать в виде:

t₀≤ d_min — 1. (13.11)

Чтобы можно было исправить все ошибки
кратностью t_ии менее, необходимо иметь минимальное
расстояние, удовлетворяющее условию:

. (13.12)

В этом случае любая кодовая комбинация
с числом ошибок t_иотличается от каждой разрешённой
комбинации не менее чем вt_и+ 1 позициях. Если условие (13.12) не выполнено,
возможен случай, когда ошибки кратностиtисказят переданную
комбинацию так, что она станет ближе к
одной из разрешённых комбинаций, чем к
переданной или даже перейдёт в другую
разрешённую комбинацию. В соответствии
с этим, условие исправления всех ошибок
кратностью не болееt_иможно записать в виде:

t_и
≤(d_min
— 1) / 2 . (13.13)

Из (13.10) и (13.12) следует, что если код
исправляет все ошибки кратностью t_и,
то число ошибок, которые он может
обнаружить, равноt₀= 2∙t_и. Следует
отметить, что соотношения (13.10) и (13.12)
устанавливают лишь гарантированное
минимальное число обнаруживаемых или
исправляемых ошибок при заданномd_minи не ограничивают возможность обнаружения
ошибок большей кратности. Например,
простейший код с проверкой на чётность
сd_mi_n= 2 позволяет обнаруживать не только
одиночные ошибки, но и любое нечётное
число ошибок в пределахt₀<n.

Корректирующие возможности кодов.

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

Так, граница Плоткинадаёт верхнюю
границу кодового расстоянияd_mi_nпри заданном числе разрядовnв
кодовой комбинации и числе информационных
разрядовm, и для
двоичных кодов:

(13.14)

или

при. (13.15)

Верхняя граница Хеммингаустанавливает
максимально возможное число разрешённых
кодовых комбинаций (2^m)
любого помехоустойчивого кода при
заданных значенияхnиd_min:

, (13.16)

где
—
число сочетаний изnэлементов поiэлементам.

Отсюда можно получить выражение для
оценки числа проверочных символов:

. (13.17)

Для значений (d_min/n)
≤ 0,3 разница между границей Хемминга и
границей Плоткина сравнительно невелика.

Граница Варшамова-Гильбертадля
больших значенийnопределяет нижнюю
границу для числа проверочных разрядов,
необходимого для обеспечения заданного
кодового расстояния:

. (13.18)

Отметим, что для некоторых частных
случаев Хемминг получил простые
соотношения, позволяющие определить
необходимое число проверочных символов:

дляd_min= 3,

дляd_min= 4.

Блочные коды с d_min= 3 и 4 в литературе обычно называют кодами
Хемминга.

Все приведенные выше оценки дают
представление о верхней границе числаd_minпри фиксированных значенияхnиmили оценку снизу числа проверочных
символовkпри заданныхmиd_min.

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

Соседние файлы в папке ЛБ_3

#
#
14.04.2015937 б70KodHemmig.m
#
14.04.20150 б62ЛБ_3.exe

Все помехоустойчивые коды делятся на блоковые и непрерывные (их называют также цепные или рекуррентные). При блоковом кодировании данные передаются отдельными блоками (словами, кодовыми комбинациями). При этом поступающие в кодер символы, разбиваются на блоки по k информационных символов. В кодере этот блок информационных символов преобразуется в блок из кодовых символов, где п называется длиной кода. Добавленные при кодировании r = n – k символов являются проверочными. Такой блоковый код принято обозначать как (n, k) – код. Величину R = k / n называют скоростью кода, а величину, обратную скорости, R_и = n / k называют избыточностью кода.

Проверочные символы являются избыточными, они необходимы для обнаружения и (или) исправления ошибок, возникших при передаче. Существуют безызбыточные (примитивные) коды. У этих кодов проверочных символов нет (n = k), поэтому у них самая высокая скорость кода R = 1, но они не способны обнаруживать ошибки.

Ошибки при передаче кодового слова возникают потому, что некоторые из переданных символов могут быть приняты неверно. Принцип обнаружения ошибок заключается в следующем. Если блоковый (n, k) – код имеет основание (количество символов в используемом алфавите) q, то возможно Q = qⁿ различных кодовых слов. Для передачи же используются только Q_р = q^k кодовых слов, которые называются разрешенными. Остальные Q_з = Q – Q_р слов априорно для передачи не используются и называются запрещенными.

В дальнейшем будут рассматриваться только двоичные коды, у которых алфавит состоит из двух символов 0 и 1, т. е. с основанием q = 2.

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

Пример 1. Требуется передача сообщения о наступлении одного из четырех возможных событий A, B, C, D. Эти события представлены информационными словами 00, 01, 10, 11 соответственно. При передаче этих слов безызбыточным кодом все возможные комбинации являются разрешенными. Поэтому достаточно искажения хотя бы одного символа, чтобы сообщение было принято неверно. Так, если передавалось сообщение A в виде кодового слова 00, а принято было слово 01, то декодер, найдя в таблице такое разрешенное слово, вынесет решение о приеме сообщения B.

Если к вышеперечисленным информационным словам добавить по одному избыточному символу, поставив в соответствие разрешенные слова 000, 011, 101, 110, то искажение одного символа в переданном слове можно обнаружить. Так, если передавалось сообщение A в виде кодового слова 000, а принято было слово 001, то декодер, не найдя в таблице такого разрешенного слова, объявит принятое слово запрещенным и сообщит об обнаружении ошибки в слове. Однако если было принято слово 011, то декодер вынесет решение о приеме сообщения B.

Для сравнения слов необходимо задать метрику, т. е. способ измерения расстояний между кодовыми словами. Известно несколько способов выбора метрики, из которых наиболее распространенным является метрика Хэмминга. Расстоянием Хэмминга между двумя кодовыми словами называется количество несовпадающих символов в этих словах. Важнейшей характеристикой блочного кода является кодовое расстояние – d, оно равно наименьшему расстоянию из всех возможных для данного кода.

Пример 2. Для передачи используются три разрешенных слова 000, 100, 111. Расстояние между первым и вторым словами равно 1, между вторым и третьим словами – 2, а между первым и вторым – 3. Кодовое расстояние для данного кода d = 1.

Очевидно, что у безызбыточного кода d = 1, так как между любой парой его слов расстояние равно единице. Этот код не позволяет обнаруживать ошибки. Приведенный в примере 1 избыточный код (он называется кодом с проверкой на четность) имеет d = 2. Он позволяет гарантировано обнаружить однократную ошибку.

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

Можно заметить, что максимальная кратность гарантировано обнаруживаемой ошибки t_о = d – 1. Действительно, при возникновении необнаруженной ошибки одно разрешенное слово должно превратиться в другое разрешенное слово. А для этого надо, чтобы кратность возникшей ошибки была не менее d, поскольку все разрешенные слова по определению кодового расстояния различаются не менее, чем на d символов. Если же принятое кодовое слово хотя бы на один символ отличается от разрешенных кодовых слов, то будет зафиксировано появление ошибки.

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

Пример 3. Для передачи используется два разрешенных кодовых слова 000 и 111. Было принято слово 001, на беглый взгляд оно больше похоже на 000, чем на 111. Действительно, слово 001 от первого разрешенного слова отличается на один символ, а от второго на два. Так как однократная ошибка вероятнее двукратной, то скорее всего было передано первое слово и в нем исказился один символ. Декодер принимает решение по минимуму расстояния Хэмминга и объявляет принятым разрешенное слово 000.

В
рассмотренном примере код имеет d = 3, он позволяет гарантировано исправлять однократную ошибку. Можно заметить, что максимальная кратность гарантировано исправляемой ошибки :

где [x] –целая часть числа x.

Существует так называемый прием со стиранием. Это частный случай приема с мягким решением. Его особенность состоит в том, что решающее устройство имеет область неопределенности, в которую попадают все сигналы, не превысившие установленный порог. Решающее устройство выдает при этом специальный символ, заменяющий неуверенно принятый сигнал. Этот символ оказывается, таким образом, «стертым». Так, при передаче двоичным кодом на выходе решающего устройства появляется один из трех символов: 0, 1 и символ стирания Х.

Восстановить стертые знаки часто оказывается легче, чем исправить ошибочные. Это обусловлено тем, что местонахождение стертых знаков известно, так как оно обозначено символом стирания Х, тогда как местоположение ошибок неизвестно, и каждый из знаков 0 или 1 может быть как верным, так и неверным.

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

Для того, чтобы код мог одновременно исправлять t ошибок и восстанавливать s стертых символов кодовое расстояние должно быть:

Преимущество кодов со стираниями очевидно: например, при d = 3 такой код может как и обычный исправить одиночную ошибку, но может восстановить два стертых символа.

Описанный выше метод кодирования и декодирования, основанный на запоминании таблицы разрешенных слов, называется универсальным, поскольку годится для всех блочных кодов. Однако этот метод практически не применяется из-за сложности реализации и низкого быстродействия. Если длина информационного слова достаточно велика, то требуется большой объем памяти для хранения всех разрешенных слов. Кроме того, сравнение принятого слова со всей таблицей может продолжаться очень долго, что недопустимо при работе в режиме реального времени. Поэтому созданы другие методы кодирования и декодирования блочных кодов, в которых используется не поиск разрешенных слов, а математические операции над информационными и проверочными символами.

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

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

Если в кодере используются лишь линейные операции над поступающими информационными символами, то код называется линейным. Принцип кодирования и декодирования линейного кода заключается в системе линейных уравнений, в которую входят информационные и проверочные символы. Для каждого кода эта система своя. Рассмотрим её на примере кода (7, 4), имеющего d = 3.

a₁  а₂  а₃  а₅ = 0

а₂  а₃  а₄  а₆ = 0

а₁  а₂  а₄  а₇ = 0

где  — знак сложения по модулю 2, символы а₁, а₂, а₃, а₄ являются информационными, а символы а₅, а₆, а₇ – проверочными. При кодировании проверочные символы вычисляются из информационных так, чтобы они удовлетворяли системе уравнений. При декодировании символы принятого слова подставляются в систему уравнений и вычисляется её правая часть. Эта правая часть представляет собой вектор, который называется исправляющим вектором или синдромом. Анализ синдрома позволяет исправлять ошибки. Каждому возможному синдрому соответствует номер искаженного символа.

Синдром	Номер искаженного символа
000	Ошибок не обнаружено
101	1
111	2
110	3
011	4

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

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

Где левая часть матрицы — единичная матрица, соответствующая информационным символам, а правая часть матрицы соответствует проверочным символам. Схема кодирования строится на основе производящей матрицы. Кодер состоит из k-элементного регистра для информационного слова и n – k сумматоров по модулю 2. Элементы правой части производящей матрицы p_ij отвечают за вычисление проверочных символов. Они показывают связь i-ой ячейки регистра с j-м сумматором. Если p_ij = 1, то связь есть, если p_ij = 0 , то связи нет.

Д
ля декодирования требуется проверочная матрица H, содержащая n – k строк и n столбцов. В каждой строке этой матрицы единицы находятся в тех разрядах, которые входят в соответствующее проверочное уравнение. Для рассмотренного кода Хэмминга (7, 4) проверочная матрица будет иметь вид:

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

Содержание

1 Исправление ошибок в помехоустойчивом кодировании
2 Параметры помехоустойчивого кодирования
3 Контроль чётности
4 Классификация помехоустойчивых кодов
5 Код Хэмминга
- 5.1 Декодирование кода Хэмминга
- 5.2 Расстояние Хэмминга
6 Помехоустойчивые коды
- 6.1 Компромиссы при использовании помехоустойчивых кодов
- 6.2 Необходимость чередования (перемежения)

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

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

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

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

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

запрос повторной передачи (Automatic Repeat reQuest, ARQ): с помощью помехоустойчивого кода выполняется только обнаружение ошибок, при их наличии производится запрос на повторную передачу пакета данных;
прямое исправление ошибок (Forward Error Correction, FEC): производится декодирование помехоустойчивого кода, т. е. исправление ошибок с его помощью.

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

Исправление ошибок в помехоустойчивом кодировании

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

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

Допустим есть 4 символа информации, А, B, С,D, и эту информацию повторяем несколько раз. В процессе передачи информации по каналу связи, где-то возникла ошибка. Есть три пакета (A1B1C1D1|A2B2C2D2|A3B3C3D3), которые должны нести одну и ту же информацию.

мажоритарный метод

Но из картинки справа, видно, что второй символ (B1 и C1) они отличаются друг от друга, хотя должны были быть одинаковыми. То что они отличаются, говорит о том, что есть ошибка.

Необходимо найти ошибку с помощью голосования, каких символов больше, символов В или символов С? Явно символов В больше, чем символов С, соответственно принимаем решение, что передавался символ В, а символ С ошибочный.

Для исправления ошибок нужно, как минимум 3 пакета информации, для обнаружения, как минимум 2 пакета информации.

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

Первый параметр, скорость кода R характеризует долю информационных («полезных») данных в сообщении и определяется выражением: R=k/n=k/m+k

где n – количество символов закодированного сообщения (результата кодирования);
m – количество проверочных символов, добавляемых при кодировании;
k – количество информационных символов.

Параметры n и k часто приводят вместе с наименованием кода для его однозначной идентификации. Например, код Хэмминга (7,4) значит, что на вход кодера приходит 4 символа, на выходе 7 символов, Рида-Соломона (15, 11) и т.д.

Второй параметр, кратность обнаруживаемых ошибок – количество ошибочных символов, которые код может обнаружить.

Третий параметр, кратность исправляемых ошибок – количество ошибочных символов, которые код может исправить (обозначается буквой t).

Контроль чётности

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

Если нечетное количество единиц, добавляем 0.

1 0 1 0 0 1 0 0 | 0

Если четное количество единиц, добавляем 1.

1 1 0 1 0 1 0 0 | 1

Если принятый бит чётности не совпадает с рассчитанным битом чётности, то считается, что произошла ошибка.

1 1 0 0 0 1 0 0 | 1

Под кратностью понимается, всевозможные ошибки, которые можно обнаружить. В этом случае, кратность исправляемых ошибок 0, так как мы не можем исправить ошибки, а кратность обнаруживаемых 1.

Есть последовательность 0 и 1, и из этой последовательности составим прямоугольную матрицу размера 4 на 4. Затем для каждой строки и столбца посчитаем бит четности.

Прямоугольный код – код с контролем четности, позволяющий исправить одну ошибку:

прямоугольный код

И если в процессе передачи информации допустим ошибку (ошибка нолик вместо единицы, желтым цветом), начинаем делать проверку. Нашли ошибку во втором столбце, третьей строке по координатам. Чтобы исправить ошибку, просто инвертируем 1 в 0, тем самым ошибка исправляется.

Этот прямоугольный код исправляет все одно-битные ошибки, но не все двух-битные и трех-битные.

Рассчитаем скорость кода для:

1 1 0 0 0 1 0 0 | 1

Здесь R=8/9=0,88

И для прямоугольного кода:

Здесь R=16/24=0,66 (картинка выше, двадцать пятую единичку (бит четности) не учитываем)

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

Классификация помехоустойчивых кодов

Непрерывные — процесс кодирования и декодирования носит непрерывный характер. Сверточный код является частным случаем непрерывного кода. На вход кодера поступил один символ, соответственно, появилось несколько на выходе, т.е. на каждый входной символ формируется несколько выходных, так как добавляется избыточность.
Блочные (Блоковые) — процесс кодирования и декодирования осуществляется по блокам. С точки зрения понимания работы, блочный код проще, разбиваем код на блоки и каждый блок кодируется в отдельности.

По используемому алфавиту:

Двоичные. Оперируют битами.
Не двоичные (код Рида-Соломона). Оперируют более размерными символами. Если изначально информация двоичная, нужно эти биты превратить в символы. Например, есть последовательность 110 110 010 100 и нужно их преобразовать из двоичных символов в не двоичные, берем группы по 3 бита — это будет один символ, 6, 6, 2, 4 — с этими не двоичными символами работают не двоичные помехоустойчивые коды.

Блочные коды делятся на

Систематические — отдельно не измененные информационные символы, отдельно проверочные символы. Если на входе кодера присутствует блок из k символов, и в процессе кодирования сформировали еще какое-то количество проверочных символов и проверочные символы ставим рядом к информационным в конец или в начало. Выходной блок на выходе кодера будет состоять из информационных символов и проверочных.
Несистематические — символы исходного сообщения в явном виде не присутствуют. На вход пришел блок k, на выходе получили блок размером n, блок на выходе кодера не будет содержать в себе исходных данных.

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

систематический и несистематический код

Смотря на картинку выше, код 1 1 0 0 0 1 0 0 | 1 является систематическим, на вход поступило 8 бит, а на выходе кодера 9 бит, которые в явном виде содержат в себе 8 бит информационных и один проверочный.

Классификация помехоустойчивых кодов

Код Хэмминга

Код Хэмминга — наиболее известный из первых самоконтролирующихся и самокорректирующихся кодов. Позволяет устранить одну ошибку и находить двойную.

Код Хэмминга (7,4)

Код Хэмминга (7,4) — 4 бита на входе кодера и 7 на выходе, следовательно 3 проверочных бита. С 1 по 4 информационные биты, с 6 по 7 проверочные (см. табл. выше). Пятый проверочный бит y5, это сумма по модулю два 1-3 информационных бит. Сумма по модулю 2 это вычисление бита чётности.

Декодирование кода Хэмминга

Декодирование происходит через вычисление синдрома по выражениям:

Декодирование кода Хэмминга через синдром

Синдром это сложение бит по модулю два. Если синдром не нулевой, то исправление ошибки происходит по таблице декодирования:

Таблица декодирования. Код Хэмминга

Расстояние Хэмминга

Расстояние Хэмминга — число позиций, в которых соответствующие символы двух кодовых слов одинаковой длины различны. Если рассматривать два кодовых слова, (пример на картинке ниже, 1 0 1 1 0 0 1 и 1 0 0 1 1 0 1) видно что они отличаются друг от друга на два символа, соответственно расстояние Хэмминга равно 2.

расстояние хэмминга

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

Помехоустойчивые коды

Современные коды более эффективны по сравнению с рассматриваемыми примерами. В таблице ниже приведены Коды Боуза-Чоудхури-Хоквингема (БЧХ)

Коды Боуза-Чоудхури-Хоквингема (БЧХ)

Из таблицы видим, что там один класс кода БЧХ, но разные параметры n и k.

n — количество символов на входе.
k — количество символов на выходе.
t — кратность исправляемых ошибок.
Отношение k/n — скорость кода.
G (энергетический выигрыш) — величина, показывающая на сколько можно уменьшить отношение сигнал/шум (Eb/No) для обеспечения заданной вероятности ошибки.

Несмотря на то, что скорость кода близка, количество исправляемых ошибок может быть разное. Количество исправляемых ошибок зависит от той избыточности, которую добавим и от размера блока. Чем больше блок, тем больше ошибок он исправляет, даже при той же самой избыточности.

Пример: помехоустойчивые коды и двоичная фазовая манипуляция (2-ФМн). На графике зависимость отношения сигнал шум (Eb/No) от вероятности ошибки. За счет применения помехоустойчивых кодов улучшается помехоустойчивость.

График помехоустойчивых кодов

Из графика видим, код Хэмминга (7,4) на сколько увеличилась помехоустойчивость? Всего на пол Дб это мало, если применить код БЧХ (127, 64) выиграем порядка 4 дБ, это хороший показатель.

Компромиссы при использовании помехоустойчивых кодов

Чем расплачиваемся за помехоустойчивые коды? Добавили избыточность, соответственно эту избыточность тоже нужно передавать. Нужно: увеличивать пропускную способность канала связи, либо увеличивать длительность передачи.

Компромиссы при использовании помехоустойчивых кодов

Компромисс:

Достоверность vs полоса пропускания.
Мощность vs полоса пропускания.
Скорость передачи данных vs полоса пропускания

Необходимость чередования (перемежения)

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

Например, в канале связи шумов мало, все передается хорошо, ошибки возникают редко, но вдруг возникла импульсная помеха или замирания, которые повредили на некоторое время процесс передачи, и потерялся большой кусок информации. В среднем на блок приходится одна, две ошибки, а в нашем примере потерялся целый блок, включая информационные и проверочные биты. Сможет ли помехоустойчивый код исправить такую ошибку? Эта проблема решаема за счет перемежения.

Пример блочного перемежения:

Пример блочного перемежения кодов

На картинке, всего 5 блоков (с 1 по 25). Код работает исправляя ошибки в рамках одного блока (если в одном блоке 1 ошибка, код его исправит, а если две то нет). В канал связи отдается информация не последовательно, а в перемешку. На выходе кодера сформировались 5 блоков и эти 5 блоков будем отдавать не по очереди а в перемешку. Записали всё по строкам, но считывать будем, чтобы отправлять в канал связи, по столбцам. Информация в блоках перемешалась. В канале связи возникла ошибка и мы потеряли большой кусок. В процессе приема, мы опять составляем таблицу, записываем по столбцам, но считываем по строкам. За счет того, что мы перемешали большое количество блоков между собой, групповая ошибка равномерно распределится по блокам.

Источник

В
рассмотренном примере код имеет d = 3, он позволяет гарантировано исправлять однократную ошибку. Можно заметить, что максимальная кратность гарантировано исправляемой ошибки :

где [x] –целая часть числа x.

a₁  а₂  а₃  а₅ = 0

а₂  а₃  а₄  а₆ = 0

а₁  а₂  а₄  а₇ = 0

Синдром	Номер искаженного символа
000	Ошибок не обнаружено
101	1
111	2
110	3
011	4

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

Источник

Занятие 7

Разбор задачек по контрольной работе.

№5, №4, №3 – все типовые (3 балла за каждую)

№2 (5 баллов). Цифровая фотография имеет размер 800*600 пикселей. Она сохраняется как 16цветный рисунок. Размер файла 215КБ. Найти избыточность рисунка.

Решение: Число элементов рисунка: No=800*600=480000. Максимальное количество информации, содержащееся в одном элементе Hmax(A)=log16=4 бит/элемент. Среднее количество информации, приходящееся на один элемент, т.е. энтропия: H(A)=215*8*1024/480000=3.67 бит/элемент.

Избыточность телевизионного кадра: 1 H(A) =1-3.67/4=0.08 или 8,25%

Hmax (A)

№1 (10 баллов). Датчик температуры выдает показания каждую минуту. Диапазон измерений температуры 0 до 20 с шагом квантования 1 С. Время измерений 5 минут. Найти макс. энтропию датчика температур.

Решение: Максимальная энтропия определяется алфавитом сообщений. Из диапазона измерений

можем найти возможное число показаний датчика: n Nmax Nmin 1. Оно равно 21. За пять минут

датчик выдаст пять показаний, в каждый из которых может быть одно из 21 показаний. Т.е. всего возможно 215 комбинаций показаний – это и есть алфавит сообщений. Т.к. нет никакой дополнительной информации о формате представляемых данных, то определяем Hmax(A)=log2K=log2215 = 21.96 бит. Или полагая, что за время измерений будет выдано Nt сообщений, каждое из которых несет log2n бит информации, получим аналогичное выражение

Hmax(A)=Nt*log2n=5*log221 = 21.96 бит.

Занятие 7. Помехоустойчивое кодирование

Теория.

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

Ошибки, возникающие в канале, принято характеризовать параметром q, называемом кратностью ошибки. Если при передаче комбинации 3 разряда изменили свое значение (с 1 на 0 или наоборот), то говорят, что произошла ошибка кратностью 3. Помехоустойчивые коды характеризуются различной обнаруживающей и разрешающей способностью. Это есть максимальная кратность qо гарантированно обнаруживаемых ошибок и максимальная кратность qи гарантированно исправляемых ошибок. Если q>qо или q>qи, то одни ошибки могут быть обнаружены или исправлены а другие — нет.

Значения qо и qи зависят от основного параметра избыточного кода — минимального кодового расстояния по Хэммингу — dmin.

Определение 2. Расстоянием по Хэммингу d(b1,b2) между двумя кодовыми комбинациями b1 и b2 называется число позиций этих комбинаций, в которых кодовые символы b1i и b2i не совпадают (i=1,2,…n).

n
d(b1,b2 ) (b1i b2i ), где знак	обозначает логическую операцию «исключающее или»,
i 1

результаты выполнения которой представлены ниже:

0 0 0;1 1 0;0 1 1;1 0 1

Определение 3. Минимальным кодовым расстоянием dmin для заданного кода называется минимальное расстояние по Хэммингу между всеми парами разрешенных кодовых комбинаций.

Пусть код обладает определенным dmin. Тогда он позволяет обнаруживать ошибку кратностью q<dmin. Таким образом, максимальная кратность обнаруживаемых ошибок — qо=dmin-1. Тот же код позволяет исправлять ошибки кратностью q<dmin/2. Максимальная кратность исправляемых ошибок:

qи=(dmin-1)/2 при нечетном dmin, qи=dmin/2-1 при четном dmin.

Все ошибки кратностью q<=qо будут гарантированно обнаружены, а ошибки q<=qи будут гарантированно исправлены.

Задачи по теме

7.1

Аналоговый сигнал путем дискретизации во времени и квантования по уровню превращается в импульсную последовательность с числом уровней К=128. Найти длину кодовой комбинации. Найти избыточность кода, если число разрядов кода увеличить на 3.

Решение: Если длина кодовой комбинации n, то двоичным кодом можно закодировать K=2k сообщений. Отсюда k=log2K=7. Если число разрядов кода увеличить на 3, то в коде будет 7 разрядов, несущих полезную информацию и 3 избыточных разряда. Поэтому избыточность кода будет равна: =1-7/10=0.3.

7.2 (3 балла)

Алфавит источника объёмом К=256 кодируется 15-разрядным двоичным кодом. Найти избыточность кода, а также число информационных и избыточных разрядов.

Решение: Если длина кодовой комбинации n, то двоичным кодом можно закодировать K=2k сообщений. Отсюда k=log2K=8. Если алфавит кодируется 15-разрядным кодом, то в коде будет 8 разрядов, несущих полезную информацию и 7 избыточных разряда. Поэтому избыточность кода будет равна: =1-8/15=0.47.

7.3.

Комбинации n-разрядного двоичного кода содержат k информационных символов. Определить долю обнаруживаемых и исправляемых таким кодом ошибок из числа всевозможных ошибок.

Решение: Обозначим обнаруживаемые ошибки — Ообн; исправляемые ошибки — Оисп; все возможные ошибки — О. Нам необходимо найти Ообн/О и Оисп/О. Найдем сначала количество всех возможных ошибок. Если в коде k инф. символов, то таким кодом можно закодировать К=2k сообщений. Таким образом, в канал связи передаются К кодовых комбинаций. Назовем их разрешенными и их число обозначим: Np. На рис. 1 они показаны точками b1p, b2p и т.д. В результате воздействия шума на передаваемые кодовые комбинации (Nр), они могут быть искажены, и тогда будет принята любая кодовая комбинация из числа N=2n. Комбинации кода из числа N не входящие в Nр называют запрещенными комбинациями: Nз=N-Np. Получение приемником такой комбинации говорит о том, что ошибка произошла. На рис. 1 они показаны точками bзап.

Пусть была передана кодовая комбинация b1p, При получении любой другой возможной кодовой комбинации кроме b1p будет ошибка. Поэтому число ошибок, которые могут произойти при передаче b1p определится как N-1.

b1р bзап bзап	b2р	b1р bзап bзап	b2р
dmin-1		0.5dmin-1	0.5dmin-1
	0.5dmin	0.5dmin
dmin
		dmin
а)			б)

Рис 1. К оценке обнаруживающей а) и исправляющей б) способности кода. b1р; b2р — разрешенные кодовые комбинации; bзап — запрещенные.

Столько же ошибок может дать и любая другая кодовая комбинация из числа разрешенных. Поэтому общее число возможных ошибок О=Np(N-1).

При получении кодовой комбинации из числа Nз, ошибка будет обнаружена, т.к. мы заранее знаем, что такая комбинация не может быть передана. Поэтому Ообн=Np*Nз=Np(N-Np).

Тогда получим:

O	N Np		2n 2k
обн				1 2k n
	N 1
O		2n 1

Рис.1б. объясняет принцип исправления ошибок: любая полученная bзап исправляется к ближайшей biр. Поэтому, если была передана, например, b1р, то верно исправляться будут лишь ближайшие к ней bзап (при d<dmin/2). Таким образом, общее число верно исправленных ошибок составит Nз.

Таким образом, получим:

O	исп		N Np	2n	2k	1	1
					2n
O Np (N 1)		2k (2n 1) 2k

7.4.

Число разрядов кодовой комбинации n=125; число информационных символов k=100. Вероятность ошибочной регистрации одного кодового символа — р0=0.1. Минимальное кодовое расстояние — dmin=6. Найти избыточность кода и вероятность ошибочного декодирования всей кодовой комбинации.

Решение:

Избыточность кода: =1-k/n=1-100/125=1/5=0.2.

Помехоустойчивый код решает две задачи: а) обнаружение кодов с ошибками и б) исправление этих ошибок. Ошибочное декодирование означает, что ошибка обнаружена, но не исправлена. Такая ситуация возникает тогда, когда кратность ошибки больше исправляющей, но меньше обнаруживающей способности кода: qи<q<=qо.

В нашей задаче qи=dmin/2-1=6/2-1=2; qo=dmin-1=5. Поэтому вероятность ошибочного декодирования равна суммарной вероятности ошибок кратности 3,4 и 5:

PО.Д.3 p03 =>PО.Д.3 p03 (1 p0)122 =>PО.Д.3 C1253 p03 (1 p0)122

PО.Д. C1253 p03 (1 p0)122 C1254 p04 (1 p0)121 C1255 p05 (1 p0)120

PО.Д. 9.337 10 4

Здесь 1-р0 — вероятность правильной регистрации кодового символа; Сnq — количество комбинаций из n по q, т.е. количество всех вариантов ошибки кратностью q в n-разрядной кодовой

комбинации: Cq	n!	— число сочетаний.

n	q!(n q)!
7.5 (5 баллов).
Найти вероятность	правильного декодирования кодовой комбинации при n=125; p=0.1;

dmin=6.

Решение: Правильное декодирование означает правильное обнаружение и исправление ошибок. Для заданного dmin=6 получим qи=dmin/2-1=6/2-1=2. Значит, ошибки кратности 1 и 2 будут

обнаружены и исправлены: PП.Д. C1251 p10 (1 p0 )124 C1252 p02 (1 p0 )123 =PПД 2.096 10 4

7.6. (на дом)

Определить dmin для кода, обнаруживающего пятикратную и исправляющего тройную ошибку.

Решение: по определению q

min

1, откуда d

min

1. В свою очередь,

dmin 1

или

dmin

1, откуда

2q 1

или

2(q

1). Тогда

по

данным условия задачи

dmin

min

определяется из системы:

dmin

qo 1

dmin

5 1

dmin

2qи 1 =>

dmin

2 3 1

dmin

7 => dmin=7

2(q

2(3 1)

min

Соседние файлы в папке Задачи для экзамена

Источник

запрос повторной передачи (Automatic Repeat reQuest, ARQ): с помощью помехоустойчивого кода выполняется только обнаружение ошибок, при их наличии производится запрос на повторную передачу пакета данных;
прямое исправление ошибок (Forward Error Correction, FEC): производится декодирование помехоустойчивого кода, т. е. исправление ошибок с его помощью.

Исправление ошибок в помехоустойчивом кодировании

мажоритарный метод

Для исправления ошибок нужно, как минимум 3 пакета информации, для обнаружения, как минимум 2 пакета информации.

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

где n – количество символов закодированного сообщения (результата кодирования);
m – количество проверочных символов, добавляемых при кодировании;
k – количество информационных символов.

Контроль чётности

Если нечетное количество единиц, добавляем 0.

1 0 1 0 0 1 0 0 | 0

Если четное количество единиц, добавляем 1.

1 1 0 1 0 1 0 0 | 1

Если принятый бит чётности не совпадает с рассчитанным битом чётности, то считается, что произошла ошибка.

1 1 0 0 0 1 0 0 | 1

Прямоугольный код – код с контролем четности, позволяющий исправить одну ошибку:

прямоугольный код

Этот прямоугольный код исправляет все одно-битные ошибки, но не все двух-битные и трех-битные.

Рассчитаем скорость кода для:

1 1 0 0 0 1 0 0 | 1

Здесь R=8/9=0,88

И для прямоугольного кода:

Здесь R=16/24=0,66 (картинка выше, двадцать пятую единичку (бит четности) не учитываем)

Классификация помехоустойчивых кодов

Непрерывные — процесс кодирования и декодирования носит непрерывный характер. Сверточный код является частным случаем непрерывного кода. На вход кодера поступил один символ, соответственно, появилось несколько на выходе, т.е. на каждый входной символ формируется несколько выходных, так как добавляется избыточность.
Блочные (Блоковые) — процесс кодирования и декодирования осуществляется по блокам. С точки зрения понимания работы, блочный код проще, разбиваем код на блоки и каждый блок кодируется в отдельности.

По используемому алфавиту:

Двоичные. Оперируют битами.
Не двоичные (код Рида-Соломона). Оперируют более размерными символами. Если изначально информация двоичная, нужно эти биты превратить в символы. Например, есть последовательность 110 110 010 100 и нужно их преобразовать из двоичных символов в не двоичные, берем группы по 3 бита — это будет один символ, 6, 6, 2, 4 — с этими не двоичными символами работают не двоичные помехоустойчивые коды.

Блочные коды делятся на

Систематические — отдельно не измененные информационные символы, отдельно проверочные символы. Если на входе кодера присутствует блок из k символов, и в процессе кодирования сформировали еще какое-то количество проверочных символов и проверочные символы ставим рядом к информационным в конец или в начало. Выходной блок на выходе кодера будет состоять из информационных символов и проверочных.
Несистематические — символы исходного сообщения в явном виде не присутствуют. На вход пришел блок k, на выходе получили блок размером n, блок на выходе кодера не будет содержать в себе исходных данных.

систематический и несистематический код

Классификация помехоустойчивых кодов

Код Хэмминга

Код Хэмминга (7,4)

Декодирование кода Хэмминга

Декодирование происходит через вычисление синдрома по выражениям:

Декодирование кода Хэмминга через синдром

Таблица декодирования. Код Хэмминга

Расстояние Хэмминга

расстояние хэмминга

Помехоустойчивые коды

Коды Боуза-Чоудхури-Хоквингема (БЧХ)

Из таблицы видим, что там один класс кода БЧХ, но разные параметры n и k.

n — количество символов на входе.
k — количество символов на выходе.
t — кратность исправляемых ошибок.
Отношение k/n — скорость кода.
G (энергетический выигрыш) — величина, показывающая на сколько можно уменьшить отношение сигнал/шум (Eb/No) для обеспечения заданной вероятности ошибки.

График помехоустойчивых кодов

Компромиссы при использовании помехоустойчивых кодов

Компромисс:

Достоверность vs полоса пропускания.
Мощность vs полоса пропускания.
Скорость передачи данных vs полоса пропускания

Необходимость чередования (перемежения)

Пример блочного перемежения:

Пример блочного перемежения кодов

Источник

Обнаруживаемая ошибка

Cтраница 1

Обнаруживаемые ошибки высвечиваются на табло и корректируются.
[1]

Сигналы обнаруживаемых ошибок поступают для регистрации в РМО, который представляет собой 79-разрядный регистр, реализованный на RS-триггерах.
[2]

Ожидаемая интенсивность обнаруживаемых ошибок дана в табл. 6.2 — 1 ошибка на 105 — 106 считанных перфокарт. Из этой таблицы видно, что повреждения и нарушения подачи перфокарт случаются в 3 раза чаще, чем ошибочное считывание.
[3]

Максимальную кратность goo обнаруживаемых ошибок определяют из следующих соображений.
[4]

К — кратность гарантийно обнаруживаемых ошибок.
[5]

Наиболее вероятным видом не обнаруживаемых ошибок является одновременное искажение двух символов в исходной комбинации и соответствующих им двух символов в повторяемой комбинации.
[6]

Максимальную кратность с / ю обнаруживаемых ошибок определяют из следующих соображений.
[7]

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

Эффективность системы автоматического контроля определяется долей обнаруживаемых ошибок. Для оценки эффективности используются методы: аналитический, вероятностного моделирования, экспериментальный.
[9]

Часть производителей предусматривает в спецификациях ожидаемую интенсивность обнаруживаемых ошибок для некоторых периферийных устройств. При этом предполагается, что возникновение неблагоприятных граничных режимов в системе аппаратура — носитель информации рождает случайные ошибки, для которых не существует адекватного дефекта.
[11]

В проектной практике встречаются схемы электроприводов с трудно обнаруживаемыми ошибками, которые затем выявляются при наладке и в эксплуатации. Некоторые характерные ошибочные схемы приводятся ниже.
[13]

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

В Паскале имеется несколько конструкций, которые часто лриводят к возникновению плохо обнаруживаемых ошибок.
[15]

Страницы:

Источник