Цифровая схемотехника. Исключающее ИЛИ. Контроль по четности

XOR
Графическое
обозначение
Алгебраическое
обозначение
XOR

XOR
Управляемый инвертор

XOR сравнение слов
XOR
A=B → Q=0
A≠B → Q=1
Поразрядное сравнение

Работа над ошибками
ИНФОРМАЦИЯ
Обработка
Хранение
Передача
Везде могут быть ошибки
Хранение
Передача

Работа над ошибками
http://www.comp.nus.edu.sg/~cs3235/2003-semesterI/notes4.pdf
BER (Bit Error Rate)

Работа над ошибками
Причины возникновения ошибок:
Внешние воздействия
Внутренние шумы
Деградация устройств памяти и каналов связи
Работа над ошибками:
Обнаружение
Исправление

Работа над ошибками
Пример
Можно говорить быстро и долго. Информация воспринимается правильно.

Работа над ошибками
Пример
Нужно говорить медленно и просить подтверждения.
Вероятность ошибок очень велика.
Почему такая разница?

Бриатснкие учнеые усатонвили: не важано, как
вы рсасталвятее бкувы вунрти солва, галвоне, чотб певрая и псолденяя бувкы отсавласиь
ниезмеынми, ткест бдует вопсриинмаьтся
парвиьлно.
Работа над ошибками
Пример исправления ошибок
Из интернетов
ИЗБЫТОЧНОСТЬ ИНФОРМАЦИИ

Работа над ошибками
Как избыточность может помочь?
Двоичный код
Избыточность отсутствует.
Любое сочетание 0 и 1 имеет право на существование.
Выявить ошибку невозможно
Необходимо придумать такой код у которого не все комбинации допустимы

Кодовое слово
Блоковое кодирование
Datawords
(k bit)
Codewords
(n bit)
Блок с ошибкой
Восстановленные слова

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

Кодовое слово
Что такое хороший код?
Требования
Возможность обнаружения ошибок
Возможность коррекции ошибок
Минимально допустимая избыточность
Скорость работы кодера и декодера
Простота реализации

Кодовое слово
Что такое хороший код?
Кодовые слова (codewords)
Не кодовые слова (noncodewords)
Ошибка (error)
Плохой код
Код лучше

Кодовое слово
Что такое хороший код?
Кодовые слова (codewords)
Не кодовые слова (noncodewords)
Ошибка (error)
Код лучше
Код еще лучше
Чем выше избыточность, тем надежнее система.

Кодовое слово
Хороший код. Исправление ошибок.
Код лучше
Код еще лучше
Стратегия наибольшего правдоподобия (Maximum Likelihood Decoding)
Исправление ошибок: некодовое слово превратить в ближайшее кодовое.
Бриатснкие учнеые усатонвили
Брянские ученые установили
Британские ученые установили

Кодовое расстояние
Расстояние или дистанция Хемминга
Кодовые слова (codewords)
Не кодовые слова (noncodewords)
Кодовое расстояние или расстояние Хемминга Dh расстояние между ближайшими кодовыми комбинациями. Оно определяется числом позиций, в которых их двоичные знаки не совпадают.
Чем больше Dh, тем надежнее код, но больше избыточность.
У простого двоичного кода Dh=1.
Избыточности нет – хорошо.
Помехоустойчивости так же нет – плохо.

Кодирование
Необходимы две сложные комбинаторные схемы для:
кодирования и
декодирования

Линейные коды
Простота схем кодирования и раскодирования

Обнаружение ошибок. Контроль по четности.
Четность.
A=B → Q=0
A≠B → Q=1
Четное кол-во 1
Нечетное кол-во 1
Четное кол-во 1 → Q=0
Нечетное кол-во 1 → Q=1

Обнаружение ошибок. Контроль по четности.
Сумматор по модулю 2.
Четное кол-во 1 → Q=0
Нечетное кол-во 1 → Q=1
=
Сумматор по модулю 2 (сумматор без переносов)

Обнаружение ошибок. Контроль по четности.
Исходная
Информация
(байт)
Добавочный бит четности
Хранится или передается
Кодовое слово
(информация + бит четности)
Кодовое слово ВСЕГДА имеет четное количество 1
Parity Error
Чтение (прием) кодового слова
Синдром ошибки

Обнаружение ошибок. Контроль по четности.
Кодовые слова (codewords)
Не кодовые слова (noncodewords)
Дистанция Хемминга Dh=2.
Синдром ошибки возникает при ошибке в одном бите.
Двойная ошибка останется незамеченной.
Более точно:
Нечетное количество ошибок будет замечено
Нечетное – нет.

Обнаружение ошибок. Вероятность многократных ошибок.
Синдром ошибки возникает при ошибке в одном бите.
Двойная ошибка останется незамеченной.
Достаточно условная таблица
Для двух независимых событий
Вероятность двойного события = (вер. события 1) X (вер. события 2)

Контроль по четности. Длина слова.
Вероятность одиночной битовой ошибки = 9P
Вероятность одиночной битовой ошибки = 17P

Контроль по четности. Исправление ошибок.
Идея. Перекрытие (Overlapping).
Простейший контроль по четности
Исправить = инвертировать!

Контроль по четности. Исправление ошибок.
Идея. Перекрытие (Overlapping).
codeword
dataword
Исправляет любые одинарные ошибки
Это лучше, чем просто повторить передачу
Dh=3

Исправляющие коды
Код Хемминга. Идея.
Richard W. Hamming
1915-1998
dataword
Bit Position
Bit
Степени 2
Опять контроль по четности
Вначале в позиции битов контроля по четности записываются 0

Исправляющие коды
Код Хемминга. Формирование кода.
P0=
codeword
P1=
P2=
P3=
Bit Position
Вычисляются биты контроля по четности.

Исправляющие коды
Код Хемминга. Формирование кода.
codeword
Bit Position
Это кодовое слово хранится или передается.

Исправляющие коды
Код Хемминга. Прием или чтение из памяти.
Pi0=
codeword
Pi1=
Pi2=
Pi3=
Bit Position
Ошибка
Pi0 ≠ P0
Pi1 ≠ P1
Pi2 ≠ P2
Pi3 = P3
Синдром
Ошибка в позиции 7
7

Исправляющие коды
Код Хемминга. Параметры.
Dh=3
Исправляет любую одиночную ошибку

Работа над ошибками. Исправление ошибок.
Двухмерный контроль по четности. Идея.
Two-Dimensional Parity Check
Биты четности по строкам
Биты четности по столбцам

Работа над ошибками. Исправление ошибок.
Двухмерный контроль по четности. Идея.
Two-Dimensional Parity Check
Одиночную ошибку исправляет

Работа над ошибками. Исправление ошибок.
Двухмерный контроль по четности. Идея.
Two-Dimensional Parity Check
Двойную ошибку фиксирует
Тройную ошибку фиксирует
Четвертную ошибку не обнаруживает

Классификация корректирующих кодов
Это потом

Types of Errors
Single-Bit Error:
Multiple-Bit Error:
Burst Error:
Это ошибки, имеющие одну причину

Burst Error
Пример
Burst Error:
Как исправить?
Надо превратить серию последовательных ошибок в набор одиночных.