Коды, обнаруживающие ошибки

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

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

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

Пример

Пусть безизбыточная кодовая комбинация имеет вид .

Проверочный символ , а кодовая комбинация на выходе кодера –

Код с числом единиц, кратным трем

Этот код образуется путем добавления к информационным символам двух контрольных символов (m = 2), имеющих такие значения, при которых сумма единиц в разрешенных комбинациях кратна трем.

Пример

m

На приемной стороне вес полученных кодовых комбинаций проверяется на кратность 3 (вес кодовой комбинации – число ненулевых символов в комбинации).

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

Код относится к классу разделимых и систематических.

Корреляционный код

Корреляционный код по-другому называют кодом с удвоением элементов. Здесь каждый символ двоичного безизбыточного кода кодируется двумя элементами, причем 1 преобразуется в 10, а 0 01. Таким образом, вместо комбинации 01101, например, в канал связи передается 01.10.10.01.10. Ошибка обнаруживается, если в парных элементах будут содержаться одинаковые символы, т.е. 11 или 00 вместо 10 и 01. При правильном приеме четные элементы отбрасываются и остается первоначальная комбинация.

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

Корреляционный код относится к группе разделимых и систематических.

Комбинированный инверсный код.

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

Пример

		Инверсный код
1 1 0 0 0 1	0 0 1 1 1 0	1 1 0 0 0 1 0 0 1 1 1 0
0 0 1 0 1 0	0 0 1 0 1 0	0 0 1 0 1 0 0 0 1 0 1 0

Прием комбинированного инверсного кода осуществляется в два этапа.

На 1-ом этапе суммируются единицы в первой (основной) группе символов . Если число единиц в этой части комбинации четное, то последующие контрольные символы принимаются без изменения; если число символов окажется нечетное, то контрольные символы инвертируются.

На 2-ом этапе контрольные символы сравниваются с информационными путем суммирования по модулю 2. Если передача прошла без ошибок, то результат суммирования будет нулевым. В противном случае в сумме по модулю 2 появляются единицы, что и является индикатором ошибки.

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

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

Пример

Пусть исходная комбинация имеет вид:

Предположим, что произошла однократная ошибка в информационной части, т.е. принята комбинация

После декодирования получаем:

							– чт
							Вывод: ошибка в 4-м разряде информационной части

Если принята комбинация , т.е. произошла ошибка в контрольной части, после декодирования получаем:

							– нч
							Вывод: ошибка в 5-м разряде проверочной части.

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

Примеры решения задач

Задачи на меру Хартли

1. Чему равно максимальное количество информации, переносимое 2 сообщениями 5-значного 8-ричного кода?

Решение: количество информации, переносимое 1 сообщением, определяется выражением: . По условию задачи: , ,

бит. Количество информации, переносимое 2 сообщениями: бит.

2. Определить объем используемого алфавита, если известно, что 16-значное сообщение, составленное из этого алфавита, несет в себе 32 бита информации.

Решение: по условию задачи n=16, I=32 бита, m=?

, ; . .

3. Чему равна длина сообщения, составленного из 4-буквенного алфавита, если известно, что количество информации, переносимое 1 сообщением, равно 20 бит?

Решение: по условию задачи I=20 бит, m=4, n=?

; n=10.

Задачи на избыточность сообщений

1. Абсолютная избыточность сообщений, составленных из m-буквенного алфавита, равна 0,7 бит, а среднее количество информации, переносимое одним знаком сообщения, – 1,3 бита. Определить объем используемого алфавита.

Решение: абсолютная избыточность определяется выражением (2.1). , где – объем используемого алфавита. определяет среднее количество информации. переносимое одним знаком сообщения. По условию задачи =1,3 бит. Следовательно, . . m=4.

2. Информационная избыточность сообщений, составленных из 8-буквенного алфавита, равна 0,3. Определить среднее количество информации, приходящееся на 1 знак такого сообщения.

Решение: информационная избыточность определяется выражением ; . По условию задачи m=8; D=0,3. Следовательно, . Среднее количество информации, приходящееся на 1 знак такого сообщения, = = бит.

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

Решение: информационная избыточность

=

Задачи на эффективное кодирование

1. Закодировать по методике Хаффмена следующие буквы первичного алфавита , , , , . В скобках указаны вероятности появления букв в сообщении. Вероятность определить.

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

2. Закодировать по методике Шеннона-Фано следующие буквы первичного алфавита , , , , . Вероятность определить.

Решение:

Задачи на кодирование обнаруживающими кодами

1.Закодировать кодом с проверкой на четность следующие комбинации:

а). ; б).

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

2.Закодировать кодом с числом 1 кратным 3 следующие комбинации: а). ; б). ; с).

В данном коде всегда m=2, которые выбираются так, чтобы обеспечить вес полной комбинации кратным 3.

3.Корреляционный код (код с удвоением элементов). Каждый информационный символ представляется двумя символами: , . Если информационная комбинация имеет вид 01101, то в корреляционном коде ей будет соответствовать комбинация 0110100110.

4.В комбинированном инверсном коде . Кодирование осуществляется в следующей последовательности: сначала подсчитывается вес (число 1) в информационной части. Если он оказывается четным, тогда контрольная часть повторяет информационную, если нечетным – контрольная часть получается в результате инвертирования информационной:

1).

2).

Задачи на декодирование обнаруживающих кодов

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

Решение:

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

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

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

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

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

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

Если в результате декодирования получены все 0 и одна 1, значит произошла однократная ошибка в контрольной части. Следовательно, информационная часть достоверна и ее следует перевести в десятичный код.

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

Пример задания по контрольной работе – часть 2

1. Определить объем используемого алфавита, если известно, что 10-значное сообщение, составленное из этого алфавита, несет в себе 20 бит информации.

2. Закодировать по методике Хаффмена следующие буквы первичного алфавита: , , , , , . Вероятность определить.

3. Информационная избыточность сообщений, составленных из 8-буквенного алфавита, равна 0,3. Определить среднее количество информации, приходящееся на 1 знак такого сообщения.

4. Комбинация комбинированного инверсного кода имеет вид: 110111111111. Какое число передавалось?

5. Закодировать корреляционным кодом следующую комбинацию 11111001.