Код с проверкой на чётность.

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

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

Обнаруживающие коды

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

Обнаружение ошибок при декодировании производится путем проверки принятых комбинаций на четность. Нарушение четности произойдет при появлении ошибок нечетной кратности. Это позволяет обнаружить такие ошибки при проверке. Появление четных ошибок не приводит к изменению четности, поэтому такие ошибки не обнару­живаются. Проверка на четность сводится к определению суммы всех символов кодовой комбинации по модулю 2:

 

 Корректирующие коды

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

Принцип построения кода с проверкой на чётность

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

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

Кодер и декодер
Пример:

Начальные данные: 1111
Данные после кодирования: 11110 (1 + 1 + 1 + 1 = 0 (mod 2))
Принятые данные: 10110 (изменился второй бит)
Как мы видим, количество единиц в принятом пакете нечетно, следовательно, при передаче произошла ошибка.

Возможности кода с проверкой на чётность

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

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

 15. Коды Хэмминга.

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

Общая теория исправляющих кодов Хэмминга заключается в следующем. Если имеется n-значный двоичный код, то общее число возможных кодовых комбинаций – слов, передаваемых с помощью этого кода, равно:

N = ,

причем, в силу равномерности кода, количества букв в словах (длины слов) равны между собой и равны n

 Понятие кодового расстояния

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

d_V = min d(x, y), x ≠ y и x, y Î V.

Для двоичного кода V под расстоянием понимается расстояние Хэмминга.

Зависимость обнаружения ошибки от кодового расстояния

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

То есть, ошибка у кодовой комбинации с D=1 обнаружена быть не может. Если же расстояние между кодовыми словами, разрешенными к использованию, равно двум (D=2), то появление одиночной ошибки переводит кодовое слово в соседнее кодовое слово, запрещенное к передаче, и ошибка обнаруживается

 

 Зависимость исправления ошибки от кодового

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

 

Кодовое расстояние для борьбы с помехами

Характеристики корректирующих кодов

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

Почти все блочные коды относятся к разделимым кодам, кодовые комбинации которых состоят из двух частей: информационной и проверочной. При общем числе n символов в блоке число информационных символов равно k, а число проверочных символов

 

r = n – k. (2)

 

К основным характеристикам корректирующих кодов относятся:

− число разрешённых и запрещённых кодовых комбинаций;

− избыточность кода;

− минимальное кодовое расстояние;

− число обнаруживаемых или исправляемых ошибок;

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

16. Теорема Котельникова.

● Понятие спектра

Распределение интенсивности электромагнитного излучения по частотам или по длинам волн.

● Теорема Котельникова

Любая функция, спектр которой не содержит частот, выше F Гц, полностью определяется своими мгновенными значениями, следующими друг за другом через интервал времени равный 1/2F секунд.

Положение этой теоремы распространяется на функции с ограниченным спектром, т.е. спектр которых не содержит частот выше некоторой граничной частоты F герц.

Если квантовать непрерывную функцию с интервалом t = 1/2F секунд, и передавать эти отсчеты по каналу связи, то функцию можно восстановить точно даже в те интервалы времени, в которые измерение не проводилось.

● Математическая запись теоремы Котельникова

 

● График функции отсчетов

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

Если сместить начало координат в точку отсчета, то есть, принять:

тогда соотношение, определяющее функцию отсчетов примет вид:

А это, как видим, 1-ый замечательный предел.

Функция имеет свойство: во всех точках отсчета она равна нулю, кроме нулевой, то есть равна 1 при и равна 0 при

где n = ±1, ±2, ±3, …

 

● Относительная точность восстановления сигнала

Относительная точность восстановления есть отношение энергии ошибки к энергии полезного сигнала.

Здесь S(w) - спектр фукции f(t)

17. Квантование по уровню.

● Дисперсия шума квантования.

Всякий раз, когда первичный сигнал находится в интервале от Xk-1/2 до Xk+1/2, будет передаваться значение уровня X_k.

Дельта здесь - шаг квантования.

● Понятие квантования по уровню

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

 

● Равномерное и неравномерное квантование

 

При равномерном квантовании весь диапазон изменения переменной от минимального значения - Хm до максимального значения Хm делится на (m-1) равных частей (рисунок 7.14), а при неравномерном на (m-1)  неравных частей.

Рисунок 7.14 – Шкалы равномерного (а) и неравномерного квантования (б)

● Ошибка квантования

● Дисперсия шума квантования

См выше.

● Понятие оптимального квантования по уровню

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

Оптимальное квантование приводит к заметному уменьшению дисперсии ошибки квантования.