кодирование с исправлением ошибок информатика

Урок 9
§6. Кодирование с обнаружением ошибок

Содержание урока

Коды с исправлением ошибок

Коды с исправлением ошибок

Значительно сложнее исправить ошибку сразу (без повторной передачи данных), однако в некоторых случаях и эту задачу удается решить. Для этого ещё больше увеличивают избыточность кода (добавляют «лишние» биты).

Когда вы говорите по телефону, иногда приходится повторять какието фразы, если собеседник не понял вас из-за помех. Эту идею можно использовать и для компьютеров, например применить код, в котором каждый бит повторяется трижды: вместо каждого нуля будем передавать кодовое слово 000, а вместо каждой единицы — кодовое слово 111.

При передаче сообщения каждый передаваемый бит повторяется три раза подряд. Могли ли быть переданы без ошибок такие сообщения?

При передаче каждой тройки одинаковых битов произошло не более одной ошибки. Какие биты пытались передать, если получены тройки битов:

001 010 011 100 101 110?

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

Восстановите битовые цепочки (без утроения), которые передавались.

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

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

Попробуйте придумать другой трёхбитовый код (содержащий два кодовых слова), который позволяет исправлять одну ошибку и обнаруживать одну или две ошибки. Что общего в коде с утроением битов и в вашем коде?

Кроме простого дублирования битов есть и другие, более сложные помехоустойчивые коды. Например, предположим, что передаются сообщения, содержащие только четыре буквы — «П», «О», «Р», «Т». Для кодирования букв используются 5-битные кодовые слова (рис. 2.9).

Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора различаются не менее чем в трёх битах. В этом случае говорят, что расстояние Хэмминга между кодовыми словами больше или равно трём. Например, слова «П» — 111.11 и «О» — 11000 различаются в трёх последних битах, а слова «П» — 11111 и «Р» — 00100 — в четырёх битах (они подчёркнуты). Это позволяет обнаруживать и даже исправлять ошибки.

Для передачи данных использовался код, заданный на рис. 2.9. Принята цепочка 00110. Определите букву, код которой отличается от этой цепочки меньше всего.

Для передачи данных использовался код, заданный на рис. 2.9. Принята цепочка 10101. Определите знаки, коды которых отличаются от этой цепочки меньше всего.

Для передачи данных использовался код, заданный на рис. 2.9. При передаче каждого кодового слова произошло не более двух ошибок. Декодируйте сообщение, исправив ошибки: 00111 11100 11110 11000 00000 01110 11011 11100 00011 11000

Если ошибку исправить нельзя, поставьте символ «*».

В каком случае при использовании кода, заданного на рис. 2.9:

а) можно обнаружить ошибки, а исправить нельзя;
б) нельзя даже обнаружить ошибки?

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

Следующая страница Выводы. Интеллект-карта

Cкачать материалы урока

Источник

Кодирование с исправлением ошибок

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

называется помехоустойчивым или самокорректирующимся, или кодированием с исправлением ошибок. Можно считать, что А = В = <0,1>. Кроме того, естественно предположить, что содержательное кодирование (вычисление F и выполняется на устройстве, свободном от помех, то есть F и F являются функциями в обычном смысле.

Если про источник помех С ничего не известно, то функции F и F не могут быть определены, за исключением тривиальных случаев, когда 5=0 или |SI = 1. Таким образом, для решения поставленной задачи необходимо иметь описание возможных ошибок (проявлений помех).

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

> 0 —>1, 1 —>0 — ошибка типа замещения разряда;

>• е —>1, 8 —? 0 — ошибка типа вставки разряда.

Канал характеризуется верхними оценками количества ошибок каждого типа, которые возможны при передаче через канал сообщения определённой длины п. Общая характеристика ошибок канала (то есть их количество и типы) обозначается S = (Si, S 2, 1 (то есть разряд восстанавливается методом «голосования»). Это кодирование кажется помехоустойчивым для данного канала, однако на самом деле это не так. Дело в том, что хотя можно предполагать, что при передаче сообщения длины 3п возможно не более трех ошибок типа замещения разряда, но места этих ошибок совершенно необязательно распределены равномерно по всему сообщению. Ошибки замещения могут произойти в соседних разрядах, и метод голосования восстановит разряд неверно. Чтобы метод голосования сработал, вместо одного сообщения длины 3п придётся передать три сообщения длины п, то есть уменьшить втрое скорость передачи потока сообщений через канал.

Источник

Конспект для учителя по теме «Кодирование с исправлением ошибок»

В статье размещена информация о кодировании с исправлением ошибок, в конце представлено домашнее задание. Материал актуален для подготовки к ЕГЭ.

Введение

Ключевые слова:

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

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

Простейший вариант — добавить в конец блока данных дополнительный бит, который будет равен 1, если в основном сообщении нечётное число единиц, и равен 0 для сообщения с чётным числом единиц. В результате в новом блоке всегда будет чётное число единиц. Этот дополнительный бит называется битом чётности. Бит чётности используется при передаче данных в компьютерных сетях.

К каждому из этих двухбитных сообщений добавьте бит чётности (так, чтобы общее число единичных битов в каждом сообщении стало чётным):

Сообщения передаются с битом чётности. Какие из этих сообщений были переданы с ошибкой?

00101 0011010101 1001001010011

Как вы думаете, можно ли вместо бита чётности добавлять «бит нечётности», который делает общее число единичных битов в блоке данных нечётным?

К каждому из этих сообщений добавьте бит чётности;

1000 0110 1011101011 11111111

При передаче сообщения с битом чётности произошли две ошибки. Сможет ли обнаружить ошибку принимающая сторона? А если ошибок будет три? Четыре?

Получено сообщение с битом чётности, в котором оказалось нечётное число единиц. Можно ли сказать, в каком именно бите произошла ошибка?

Если при передаче изменились два бита, чётность не меняется, и такая ошибка не обнаруживается. Однако на практике две ошибки в одном небольшом (например, 8-битном) блоке данных могут появиться очень редко.

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

Коды с исправлением ошибок

Значительно сложнее исправить ошибку сразу (без повторной передачи данных), однако в некоторых случаях и эту задачу удается решить. Для этого ещё больше увеличивают избыточность кода (добавляют «лишние» биты).

Когда вы говорите по телефону, иногда приходится повторять какието фразы, если собеседник не понял вас из-за помех. Эту идею можно использовать и для компьютеров, например применить код, в котором каждый бит повторяется трижды: вместо каждого нуля будем передавать кодовое слово 000, а вместо каждой единицы — кодовое слово 111.

При передаче сообщения каждый передаваемый бит повторяется три раза подряд. Могли ли быть переданы без ошибок такие сообщения?

При передаче каждой тройки одинаковых битов произошло не более одной ошибки. Какие биты пытались передать, если получены тройки битов:

001 010 011 100 101 110?

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

Восстановите битовые цепочки (без утроения), которые передавались.

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

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

Попробуйте придумать другой трёхбитовый код (содержащий два кодовых слова), который позволяет исправлять одну ошибку и обнаруживать одну или две ошибки. Что общего в коде с утроением битов и в вашем коде?

Кроме простого дублирования битов есть и другие, более сложные помехоустойчивые коды. Например, предположим, что передаются сообщения, содержащие только четыре буквы — «П», «О», «Р», «Т». Для кодирования букв используются 5-битные кодовые слова (рис. 2.9).

Рис. 2.9

Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора различаются не менее чем в трёх битах. В этом случае говорят, что расстояние Хэмминга между кодовыми словами больше или равно трём. Например, слова «П» — 111.11 и «О» — 11000 различаются в трёх последних битах, а слова «П» — 11111 и «Р» — 00100 — в четырёх битах (они подчёркнуты). Это позволяет обнаруживать и даже исправлять ошибки.

Для передачи данных использовался код, заданный на рис. 2.9. Принята цепочка 00110. Определите букву, код которой отличается от этой цепочки меньше всего.

Для передачи данных использовался код, заданный на рис. 2.9. Принята цепочка 10101. Определите знаки, коды которых отличаются от этой цепочки меньше всего.

Для передачи данных использовался код, заданный на рис. 2.9. При передаче каждого кодового слова произошло не более двух ошибок. Декодируйте сообщение, исправив ошибки: 00111 11100 11110 11000 00000 01110 11011 11100 00011 11000

Если ошибку исправить нельзя, поставьте символ « ».

В каком случае при использовании кода, заданного на рис. 2.9:

а) можно обнаружить ошибки, а исправить нельзя;
б) нельзя даже обнаружить ошибки?

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

Выводы

Интеллект-карта

Рис. 2.10

Домашнее задание

1. Почему код с обнаружением и/или исправлением ошибок должен быть избыточным?
2. Сравните коды, использующие бит чётности и коды, использующие контрольную сумму. Какие достоинства и недостатки имеет каждый метод?
3. Зачем нужны коды, которые позволяют обнаружить ошибки, но не позволяют их исправить?
4. Сравните код, в котором каждый бит повторяется три раза, и код на рис. 2.9. Какой из них более экономичный, т. е. требует меньше «лишних» битов?
5. Как вы думаете, почему бы не использовать везде только помехоустойчивые коды?

Источник

Конспект для ученика по теме «Кодирование с исправлением ошибок»

Изучив статью, Вы узнаете, что такое помехоустойчивый код и интеллект-карта, а также, в конце конспекта находится домашнее задание. Материал актуален для подготовки к ЕГЭ.

Введение

Ключевые слова:

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

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

Простейший вариант — добавить в конец блока данных дополнительный бит, который будет равен 1, если в основном сообщении нечётное число единиц, и равен 0 для сообщения с чётным числом единиц. В результате в новом блоке всегда будет чётное число единиц. Этот дополнительный бит называется битом чётности. Бит чётности используется при передаче данных в компьютерных сетях.

К каждому из этих двухбитных сообщений добавьте бит чётности (так, чтобы общее число единичных битов в каждом сообщении стало чётным):

Сообщения передаются с битом чётности. Какие из этих сообщений были переданы с ошибкой?

00101 0011010101 1001001010011

Как вы думаете, можно ли вместо бита чётности добавлять «бит нечётности», который делает общее число единичных битов в блоке данных нечётным?

К каждому из этих сообщений добавьте бит чётности;

1000 0110 1011101011 11111111

При передаче сообщения с битом чётности произошли две ошибки. Сможет ли обнаружить ошибку принимающая сторона? А если ошибок будет три? Четыре?

Получено сообщение с битом чётности, в котором оказалось нечётное число единиц. Можно ли сказать, в каком именно бите произошла ошибка?

Если при передаче изменились два бита, чётность не меняется, и такая ошибка не обнаруживается. Однако на практике две ошибки в одном небольшом (например, 8-битном) блоке данных могут появиться очень редко.

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

Коды с исправлением ошибок

Значительно сложнее исправить ошибку сразу (без повторной передачи данных), однако в некоторых случаях и эту задачу удается решить. Для этого ещё больше увеличивают избыточность кода (добавляют «лишние» биты).

Когда вы говорите по телефону, иногда приходится повторять какието фразы, если собеседник не понял вас из-за помех. Эту идею можно использовать и для компьютеров, например применить код, в котором каждый бит повторяется трижды: вместо каждого нуля будем передавать кодовое слово 000, а вместо каждой единицы — кодовое слово 111.

При передаче сообщения каждый передаваемый бит повторяется три раза подряд. Могли ли быть переданы без ошибок такие сообщения?

При передаче каждой тройки одинаковых битов произошло не более одной ошибки. Какие биты пытались передать, если получены тройки битов:

001 010 011 100 101 110?

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

Восстановите битовые цепочки (без утроения), которые передавались.

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

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

Попробуйте придумать другой трёхбитовый код (содержащий два кодовых слова), который позволяет исправлять одну ошибку и обнаруживать одну или две ошибки. Что общего в коде с утроением битов и в вашем коде?

Кроме простого дублирования битов есть и другие, более сложные помехоустойчивые коды. Например, предположим, что передаются сообщения, содержащие только четыре буквы — «П», «О», «Р», «Т». Для кодирования букв используются 5-битные кодовые слова (рис. 2.9).

Рис. 2.9

Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора различаются не менее чем в трёх битах. В этом случае говорят, что расстояние Хэмминга между кодовыми словами больше или равно трём. Например, слова «П» — 111.11 и «О» — 11000 различаются в трёх последних битах, а слова «П» — 11111 и «Р» — 00100 — в четырёх битах (они подчёркнуты). Это позволяет обнаруживать и даже исправлять ошибки.

Для передачи данных использовался код, заданный на рис. 2.9. Принята цепочка 00110. Определите букву, код которой отличается от этой цепочки меньше всего.

Для передачи данных использовался код, заданный на рис. 2.9. Принята цепочка 10101. Определите знаки, коды которых отличаются от этой цепочки меньше всего.

Для передачи данных использовался код, заданный на рис. 2.9. При передаче каждого кодового слова произошло не более двух ошибок. Декодируйте сообщение, исправив ошибки: 00111 11100 11110 11000 00000 01110 11011 11100 00011 11000

Если ошибку исправить нельзя, поставьте символ « ».

В каком случае при использовании кода, заданного на рис. 2.9:

а) можно обнаружить ошибки, а исправить нельзя;
б) нельзя даже обнаружить ошибки?

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

Выводы

Интеллект-карта

Рис. 2.10

Домашнее задание

1. Почему код с обнаружением и/или исправлением ошибок должен быть избыточным?
2. Сравните коды, использующие бит чётности и коды, использующие контрольную сумму. Какие достоинства и недостатки имеет каждый метод?
3. Зачем нужны коды, которые позволяют обнаружить ошибки, но не позволяют их исправить?
4. Сравните код, в котором каждый бит повторяется три раза, и код на рис. 2.9. Какой из них более экономичный, т. е. требует меньше «лишних» битов?
5. Как вы думаете, почему бы не использовать везде только помехоустойчивые коды?

Источник

Алгоритмы обнаружения и коррекции ошибок

Пусть А и Б — две двоичные кодовые последовательности равной длины. Расстояние Хэмминга между двумя этими кодовыми последовательностями равно числу символов, которыми они отличаются. Например, расстояние Хэмминга между кодами 00111 и 10101 равно 2.

4.1. Алгоритмы коррекции ошибок

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

Код Хэмминга представляет собой блочный код, который позволяет выявить и исправить ошибочно переданный бит в пределах переданного блока. Обычно код Хэмминга характеризуется двумя целыми числами, например, (11,7), используемыми при передаче 7-битных ASCII-кодов. Такая запись говорит, что при передаче 7-битного кода используется 4 контрольных бита (7 + 4 = 11). При этом предполагается, что имела место ошибка в одном бите и что ошибка в двух или более битах существенно менее вероятна. С учетом этого исправление ошибки осуществляется с определенной вероятностью. Например, пусть возможны следующие правильные коды (все они, кроме первого и последнего, отстоят друг от друга на расстояние Хэмминга 4):

Источник