Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
13
Содержание
- 1. 13
- 2. XORГрафическоеобозначениеАлгебраическоеобозначениеXOR
- 3. XORУправляемый инвертор
- 4. XOR сравнение словXORA=B → Q=0A≠B → Q=1Поразрядное сравнение
- 5. Работа над ошибкамиИНФОРМАЦИЯОбработкаХранениеПередачаВезде могут быть ошибкиХранениеПередача
- 6. Работа над ошибкамиhttp://www.comp.nus.edu.sg/~cs3235/2003-semesterI/notes4.pdfBER (Bit Error Rate)
- 7. Работа над ошибкамиПричины возникновения ошибок:Внешние воздействияВнутренние шумыДеградация устройств памяти и каналов связиРабота над ошибками:ОбнаружениеИсправление
- 8. Работа над ошибкамиПримерМожно говорить быстро и долго. Информация воспринимается правильно.
- 9. Работа над ошибкамиПримерНужно говорить медленно и просить подтверждения. Вероятность ошибок очень велика.Почему такая разница?
- 10. Бриатснкие учнеые усатонвили: не важано, как вы
- 11. Работа над ошибкамиКак избыточность может помочь?Двоичный кодИзбыточность
- 12. Кодовое словоБлоковое кодированиеDatawords(k bit)Codewords(n bit)Блок с ошибкойВосстановленные слова
- 13. Кодовое словоВсе сообщение разбивается на слова. К
- 14. Кодовое словоЧто такое хороший код?ТребованияВозможность обнаружения ошибокВозможность коррекции ошибокМинимально допустимая избыточностьСкорость работы кодера и декодераПростота реализации
- 15. Кодовое словоЧто такое хороший код?Кодовые слова (codewords)Не кодовые слова (noncodewords)Ошибка (error)Плохой кодКод лучше
- 16. Кодовое словоЧто такое хороший код?Кодовые слова (codewords)Не
- 17. Кодовое словоХороший код. Исправление ошибок.Код лучшеКод еще
- 18. Кодовое расстояниеРасстояние или дистанция ХеммингаКодовые слова (codewords)Не
- 19. КодированиеНеобходимы две сложные комбинаторные схемы для:кодирования идекодирования
- 20. Линейные кодыПростота схем кодирования и раскодирования
- 21. Обнаружение ошибок. Контроль по четности.Четность.A=B → Q=0A≠B
- 22. Обнаружение ошибок. Контроль по четности.Сумматор по модулю
- 23. Обнаружение ошибок. Контроль по четности.ИсходнаяИнформация(байт)Добавочный бит четностиХранится
- 24. Обнаружение ошибок. Контроль по четности.Кодовые слова (codewords)Не
- 25. Обнаружение ошибок. Вероятность многократных ошибок.Синдром ошибки возникает
- 26. Контроль по четности. Длина слова.Вероятность одиночной битовой ошибки = 9PВероятность одиночной битовой ошибки = 17P
- 27. Контроль по четности. Исправление ошибок.Идея. Перекрытие (Overlapping).Простейший контроль по четностиИсправить = инвертировать!
- 28. Контроль по четности. Исправление ошибок.Идея. Перекрытие (Overlapping).codeworddatawordИсправляет любые одинарные ошибкиЭто лучше, чем просто повторить передачуDh=3
- 29. Исправляющие кодыКод Хемминга. Идея.Richard W. Hamming1915-1998datawordBit PositionBitСтепени
- 30. Исправляющие кодыКод Хемминга. Формирование кода.P0=codewordP1=P2=P3=Bit PositionВычисляются биты контроля по четности.
- 31. Исправляющие кодыКод Хемминга. Формирование кода.codewordBit PositionЭто кодовое слово хранится или передается.
- 32. Исправляющие кодыКод Хемминга. Прием или чтение из
- 33. Исправляющие кодыКод Хемминга. Параметры.Dh=3Исправляет любую одиночную ошибку
- 34. Работа над ошибками. Исправление ошибок.Двухмерный контроль по
- 35. Работа над ошибками. Исправление ошибок.Двухмерный контроль по четности. Идея.Two-Dimensional Parity CheckОдиночную ошибку исправляет
- 36. Работа над ошибками. Исправление ошибок.Двухмерный контроль по
- 37. Классификация корректирующих кодовЭто потом
- 38. Types of ErrorsSingle-Bit Error:Multiple-Bit Error:Burst Error:Это ошибки, имеющие одну причину
- 39. Burst ErrorПримерBurst Error:Как исправить?Надо превратить серию последовательных ошибок в набор одиночных.
- 40. InterleavingИсходная кодовая последовательность. Хемминг (4,3)После перемеженияBurst ErrorВосстановленная кодовая последовательность с одиночными ошибкамиЭто легко исправляется
- 41. Скачать презентанцию
XORГрафическоеобозначениеАлгебраическоеобозначениеXOR
Слайды и текст этой презентации
Слайд 5Работа над ошибками
ИНФОРМАЦИЯ
Обработка
Хранение
Передача
Везде могут быть ошибки
Хранение
Передача
Слайд 6Работа над ошибками
http://www.comp.nus.edu.sg/~cs3235/2003-semesterI/notes4.pdf
BER (Bit Error Rate)
Слайд 7Работа над ошибками
Причины возникновения ошибок:
Внешние воздействия
Внутренние шумы
Деградация устройств памяти и
каналов связи
Слайд 9Работа над ошибками
Пример
Нужно говорить медленно и просить подтверждения.
Вероятность ошибок
очень велика.
Почему такая разница?
Слайд 10Бриатснкие учнеые усатонвили: не важано, как
вы рсасталвятее бкувы вунрти
солва, галвоне,
чотб певрая и псолденяя бувкы отсавласиь
ниезмеынми, ткест
бдует вопсриинмаьтся парвиьлно.
Работа над ошибками
Пример исправления ошибок
Из интернетов
ИЗБЫТОЧНОСТЬ ИНФОРМАЦИИ
Слайд 11Работа над ошибками
Как избыточность может помочь?
Двоичный код
Избыточность отсутствует.
Любое сочетание 0
и 1 имеет право на существование.
Выявить ошибку невозможно
Необходимо придумать такой
код у которого не все комбинации допустимы
Слайд 12Кодовое слово
Блоковое кодирование
Datawords
(k bit)
Codewords
(n bit)
Блок с ошибкой
Восстановленные слова
Слайд 13Кодовое слово
Все сообщение разбивается на слова.
К словам добавляются дополнительные
биты и получаются кодовые слова или блоки, как и в
человеческом языке.Не все сочетания 0 и 1 в кодовом слове допустимы.
Информация передается или хранится в таком закодированном виде.
Ошибка в любом из битов (нескольких битах) кодового слова должна приводить к недопустимой комбинации (некодовому слову).
При приеме или чтении из памяти исходная информация восстанавливается или сопровождается сообщением об ошибке.
Блоковое кодирование
Слайд 14Кодовое слово
Что такое хороший код?
Требования
Возможность обнаружения ошибок
Возможность коррекции ошибок
Минимально допустимая
избыточность
Скорость работы кодера и декодера
Простота реализации
Слайд 15Кодовое слово
Что такое хороший код?
Кодовые слова (codewords)
Не кодовые слова (noncodewords)
Ошибка
(error)
Плохой код
Код лучше
Слайд 16Кодовое слово
Что такое хороший код?
Кодовые слова (codewords)
Не кодовые слова (noncodewords)
Ошибка
(error)
Код лучше
Код еще лучше
Чем выше избыточность, тем надежнее система.
Слайд 17Кодовое слово
Хороший код. Исправление ошибок.
Код лучше
Код еще лучше
Стратегия наибольшего правдоподобия
(Maximum Likelihood Decoding)
Исправление ошибок: некодовое слово превратить в ближайшее кодовое.
Бриатснкие
учнеые усатонвилиБрянские ученые установили
Британские ученые установили
Слайд 18Кодовое расстояние
Расстояние или дистанция Хемминга
Кодовые слова (codewords)
Не кодовые слова (noncodewords)
Кодовое
расстояние или расстояние Хемминга Dh расстояние между ближайшими кодовыми комбинациями.
Оно определяется числом позиций, в которых их двоичные знаки не совпадают.Чем больше Dh, тем надежнее код, но больше избыточность.
У простого двоичного кода Dh=1.
Избыточности нет – хорошо.
Помехоустойчивости так же нет – плохо.
Слайд 21Обнаружение ошибок. Контроль по четности.
Четность.
A=B → Q=0
A≠B → Q=1
Четное кол-во
1
Нечетное кол-во 1
Четное кол-во 1 → Q=0
Нечетное кол-во 1 →
Q=1
Слайд 22Обнаружение ошибок. Контроль по четности.
Сумматор по модулю 2.
Четное кол-во 1
→ Q=0
Нечетное кол-во 1 → Q=1
=
Сумматор по модулю 2 (сумматор
без переносов)
Слайд 23Обнаружение ошибок. Контроль по четности.
Исходная
Информация
(байт)
Добавочный бит четности
Хранится или передается
Кодовое слово
(информация + бит четности)
Кодовое слово ВСЕГДА имеет четное количество 1
Parity
ErrorЧтение (прием) кодового слова
Синдром ошибки
Слайд 24Обнаружение ошибок. Контроль по четности.
Кодовые слова (codewords)
Не кодовые слова (noncodewords)
Дистанция
Хемминга Dh=2.
Синдром ошибки возникает при ошибке в одном бите.
Двойная ошибка
останется незамеченной.Более точно:
Нечетное количество ошибок будет замечено
Нечетное – нет.
Слайд 25Обнаружение ошибок. Вероятность многократных ошибок.
Синдром ошибки возникает при ошибке в
одном бите.
Двойная ошибка останется незамеченной.
Достаточно условная таблица
Для двух независимых событий
Вероятность двойного события = (вер. события 1) X (вер. события 2)
Слайд 26Контроль по четности. Длина слова.
Вероятность одиночной битовой ошибки = 9P
Вероятность
одиночной битовой ошибки = 17P
Слайд 27Контроль по четности. Исправление ошибок.
Идея. Перекрытие (Overlapping).
Простейший контроль по четности
Исправить
= инвертировать!
Слайд 28Контроль по четности. Исправление ошибок.
Идея. Перекрытие (Overlapping).
codeword
dataword
Исправляет любые одинарные ошибки
Это
лучше, чем просто повторить передачу
Dh=3
Слайд 29Исправляющие коды
Код Хемминга. Идея.
Richard W. Hamming
1915-1998
dataword
Bit Position
Bit
Степени 2
Опять контроль по
четности
Вначале в позиции битов контроля по четности записываются 0
Слайд 30Исправляющие коды
Код Хемминга. Формирование кода.
P0=
codeword
P1=
P2=
P3=
Bit Position
Вычисляются биты контроля по четности.
Слайд 31Исправляющие коды
Код Хемминга. Формирование кода.
codeword
Bit Position
Это кодовое слово хранится или
передается.
Слайд 32Исправляющие коды
Код Хемминга. Прием или чтение из памяти.
Pi0=
codeword
Pi1=
Pi2=
Pi3=
Bit Position
Ошибка
Pi0 ≠
P0
Pi1 ≠ P1
Pi2 ≠ P2
Pi3 = P3
Синдром
Ошибка в позиции 7
7
Слайд 34Работа над ошибками. Исправление ошибок.
Двухмерный контроль по четности. Идея.
Two-Dimensional Parity
Check
Биты четности по строкам
Биты четности по столбцам
Слайд 35Работа над ошибками. Исправление ошибок.
Двухмерный контроль по четности. Идея.
Two-Dimensional Parity
Check
Одиночную ошибку исправляет
Слайд 36Работа над ошибками. Исправление ошибок.
Двухмерный контроль по четности. Идея.
Two-Dimensional Parity
Check
Двойную ошибку фиксирует
Тройную ошибку фиксирует
Четвертную ошибку не обнаруживает
Слайд 38Types of Errors
Single-Bit Error:
Multiple-Bit Error:
Burst Error:
Это ошибки, имеющие одну причину
Слайд 39Burst Error
Пример
Burst Error:
Как исправить?
Надо превратить серию последовательных ошибок в набор
одиночных.
Слайд 40Interleaving
Исходная кодовая последовательность. Хемминг (4,3)
После перемежения
Burst Error
Восстановленная кодовая последовательность с
одиночными ошибками
Это легко исправляется
