Лабораторная работа 7
Исследование процесса кодирования
Цель и содержание:
Углубить знания, по основам построения Кода Бергера Углубить знания, по основам кодирования методом "четности - нечетности" Углубить знания, по основам кодирования с проверкой на чётность Углубить знания, по основам кодирования с проверкой на нечетность Углубить знания, по основам кодирования с инверсным кодом Углубить знания, по контролирующим кодам с простым повторением Углубить знания, по основам корреляционных кодовКод Бергера
Теоретическое обоснование
Коды Бергера относятся к разряду несистематических кодов. Существует несколько вариантов построения кодов Бергера. В наиболее простом варианте кодирование происходит следующим образом: в информационной части кода подсчитывается число единиц, после чего формируются проверочные разряды, представляющие инвертированную запись этого числа в двоичной форме. Таким образом, число проверочных разрядов R равно наименьшему целому числу, превышающему log2(k), то есть R >= log2(k).
Коды Бергера предназначены для использования в ассиметричных каналах связи, где возможно только либо преобразование нулей в единицы, либо наоборот.
Преимущество кодов Бергера по сравнению с кодами с постоянным весом заключается в том, что они являются разделимыми кодами с очень простым алгоритмом построения проверочной части. В симметричных каналах такие коды обнаруживают все одиночные ошибки и некоторую часть многократных.
Кодирование
Кодовая комбинация, которую необходимо закодировать:
111011111110100111110111.
Количество единиц в слове – 19, в двоичном представлении – 10011. Инвертируем это число – 01100 – и добавляем его к исходному слову. Получаем закодированную кодовую комбинацию:
111011111110100111110111 01100.
Поскольку количество избыточных символов – 5, а длина закодированной кодовой комбинации – 29, то избыточность будет равняться (см. формулу (1)):
.
Декодирование
Декодируем полученную кодовую комбинацию:
111011111110100111110111 01100.
Зная, что количество информационных символов – 24, подсчитываем количество единиц в информационном блоке – их 19. Берем 5 избыточных символов – 01100 – и инвертируем избыточный блок – 10011. Переводим полученное число в десятичный вид – 19. Оно совпадает с количеством единиц в информационном блоке. Это означает, что ошибок, которые мы можем обнаружить, нет. Значит, отбрасываем проверочные символы и получаем декодированное сообщение:
111011111110100111110111.
Коды Бергера относятся к разряду несистематических кодов. Существует несколько вариантов построения кодов Бергера. В наиболее простом варианте кодирование происходит следующим образом: в информационной части кода подсчитывается число единиц, после чего формируются проверочные разряды, представляющие инвертированную запись этого числа в двоичной форме. Таким образом, число проверочных разрядов R равно наименьшему целому числу, превышающему log2(k), то есть R >= log2(k).
Коды Бергера предназначены для использования в ассиметричных каналах связи, где возможно только либо преобразование нулей в единицы, либо наоборот.
Преимущество кодов Бергера по сравнению с кодами с постоянным весом заключается в том, что они являются разделимыми кодами с очень простым алгоритмом построения проверочной части. В симметричных каналах такие коды обнаруживают все одиночные ошибки и некоторую часть многократных.
Кодирование методом "четности - нечетности"
Если допускается только один контрольный бит, то этот избыточный разряд добавляется к основным информационным разрядам и в нем записывается значение 1 или 0 в соответствии с условием, чтобы это значение было равно сумме информационных разрядов числа по модулю 2 для случая четности или инверсии этой суммы цифр для случая нечетности. Наличие ошибки обнаруживается в случае несовпадения значения принятого контрольного разряда со значением вновь вычисленного. Пример реализации контроля по методу четности приведен в табл.1. (единичная ошибка в контрольном бите в четвертой комбинации).
Tаблица 1
|
|
|
10101011 | 1 | 1 |
11001010 | 0 | 0 |
10010001 | 1 | 1 |
11001011 | 0 | 1 – несоответствие |
Существует модифицированный способ контроля по методу "четности-нечетности" (табл.2). Длинное слово разбивается на группы, каждая из которых содержит n разрядов. Контрольные k разрядов добавляются для контроля по строкам и столбцам в соответствии с (табл.2).
Tаблица 2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Увеличение избыточности информации позволяет не только обнаружить ошибку, но и корректировать ее.
Например:
10011 1 1
11111 0 1
01010 0 0
10100 0 0
10010 0 0
01000
00000
Проверка показывает, что ошибка имела место во второй строке и втором столбце. Разряд, содержащий информационную ошибку, находится на пересечении второй строки и второго столбца, т. е. необходимо заменить вторую единицу во второй строке на нуль.
Код с проверкой на чётность
Краткие теоретические сведения
Код с проверкой на четность образуется добавлением к группе информационных разрядов, представляющих простой (неизбыточный) код, одного избыточного (контрольного) разряда.
При формировании кодовой комбинации в контрольный разряд записывается 0 или 1 таким образом, чтобы сумма единиц в слове, включая избыточный разряд, была четной. Если при передаче информации приемное устройство обнаруживает, что в принятом слове значение контрольного разряда не соответствует четности суммы единиц слова, то это воспринимается как признак ошибки.
Минимальное кодовое расстояние этого кода dmin = 1, поэтому код с проверкой на четность обнаруживает все одиночные ошибки, а кроме того, все случаи нечетного числа ошибок (3, 5 и т. д.). При одновременном возникновении двух или любого другого четного числа ошибок код с проверкой четности не обнаруживает ошибок.
Данный код имеет небольшую избыточность и не требует больших затрат оборудования на реализацию контроля. Он широко применяется в вычислительных машинах для контроля передач информации между регистрами и для контроля считываемой информации в оперативной памяти.
Кодирование
Кодовая комбинация, которую необходимо закодировать:
111011111110100111110111.
Количество единиц в слове – 19, следовательно, проверочный разряд равен 1, поскольку тогда количество единиц в закодированной кодовой комбинации будет четное.
Закодированная кодовая комбинация:
111011111110100111110111 1.
Поскольку количество избыточных символов – 1, а длина закодированной кодовой комбинации – 25, то избыточность будет равняться (см. формулу (1)):
.
Декодирование
Декодируем полученную кодовую комбинацию:
111011111110100111110111 1.
Сумма единиц в полученном слове равна 20, то есть число четное, следовательно, одиночной, а также других нечетных ошибок нет. Поскольку мы не можем проверить наличие четных ошибок, то, считая, что их нет, просто отбрасываем проверочный разряд и получаем декодированное сообщение:
111011111110100111110111.
Код с проверкой на нечетность
Краткие теоретические сведения
Код с проверкой на нечетность аналогичен коду с проверкой на четность, только при формировании кодовой комбинации в контрольный разряд записывается 0 или 1 таким образом, чтобы сумма единиц в слове, включая избыточный разряд, была нечетной.
При контроле по нечетности контролируется полное пропадание информации, поскольку кодовое слово, состоящее из 0, относится к запрещенным.
Кодирование
Кодовая комбинация, которую необходимо закодировать:
111011111110100111110111.
Количество единиц в слове – 19, следовательно, проверочный разряд равен 0, поскольку тогда количество единиц в закодированной кодовой комбинации будет нечетное.
Закодированная кодовая комбинация:
111011111110100111110111 0.
Аналогично коду с проверкой на четность избыточность составляет:
.
Декодирование
Декодируем полученную кодовую комбинацию:
111011111110100111110111 0.
Сумма единиц в полученном слове равна 19, то есть число нечетное, следовательно, одиночной, а также других нечетных ошибок нет. Поскольку мы не можем проверить наличие четных ошибок, то, считая, что их нет, просто отбрасываем проверочный разряд и получаем декодированное сообщение:
111011111110100111110111.
Инверсный код
Краткие теоретические сведения
Кодовые комбинации инверсного кода образуются повторением исходного кодового слова. Если число единиц в исходном слове четное, оно повторяется в неизменном виде; если число единиц нечетное, то при повторении все символы исходного кодового слова инвертируются.
Для обнаружения ошибок в кодовом слове, состоящем из n = k + r символов производится две операции:
суммируются единицы, содержащиеся в первых k символах кодового слова. если число единиц четное, r последующих символов сравниваются попарно с первыми k символами; если число единиц в первых символах нечетное, последующие символы перед сравниванием инвертируются.Несовпадение хотя бы одной из пар сравниваемых кодовых символов указывает на наличие ошибки в кодовом слове.
Ошибка в кодовом слове не обнаруживается, если одновременно искажается четное число символов в исходном слове и соответствующие им кодовые символы в последовательности повторяемых r символов.
Кодирование
Кодовая комбинация, которую необходимо закодировать:
111011111110100111110111.
Количество единиц в слове – 19, то есть нечетное число, следовательно, кодовая комбинации инверсного кода образуются повторением исходного кодового слова с инвертированными битами.
Закодированная кодовая комбинация:
111011111110100111110111 000100000001011000001000.
Поскольку количество избыточных символов – 24, а длина закодированной кодовой комбинации – 48, то избыточность будет равняться (см. формулу (1)):
.
Декодирование
Декодируем полученную кодовую комбинацию:
111011111110100111110111 000100000001011000001000.
Количество единиц, содержащихся в первых 24 символах кодового слова – 19, то есть нечетное число. Значит, 24 последующих символов сравниваем попарно с инвертированным первыми 24 символами. Все символы попарно совпадают. Поскольку данный код не позволяет обнаружить ошибку, если одновременно искажается четное число символов в исходном слове и соответствующие им кодовые символы в последовательности повторяемых r символов, то, считая, что таких ошибок нет, просто отбрасываем повторяемые символы и получаем декодированное сообщение:
111011111110100111110111.
Контролирующий код с простым повторением
Контролирующий код с простым повторением основывается на повторении передачи сообщения. Сообщение передается дважды: принятое сообщение после второй передачи сравнивается с принятым после первой передачи. Если имеется несовпадения в соответствующих разрядах, то фиксируется наличие ошибки в кодовой комбинации. Этот код имеет одинаковую вероятность обнаружения ошибок по сравнению с контролирующим кодом по методу четности. Но он более защищен от влияния шумов в канале так как способен обнаруживать все ошибки в паре комбинации. Ранее упоминалось о разрядах, имеющих одинаковые позиции в первой и второй кодовых комбинациях. Этот код эффективен в случае каналов, подверженных влиянию пакетов ошибок
Корреляционный код
Краткие теоретические сведения
Кодирование корреляционным кодом производится по схеме превращения: 0 → 01, 1 → 10. Декодирование происходит обратным образом: 01 → 0, 10 → 1.
Если при передаче сообщения произошли ошибки, то декодер, обнаружив за один такт две единицы 11, либо два нуля 00, обнаружит ошибку.
Кодирование
Кодовая комбинация, которую необходимо закодировать:
111011111110100111110111.
По схеме превращения 0 → 01, 1 → 10 получаем следующую закодированную кодовую комбинацию:
101010011010101010101001100101101010101001101010.
Поскольку количество избыточных символов – 24, а длина закодированной кодовой комбинации – 48, то избыточность будет равняться (см. формулу (1)):
Декодирование
Декодируем полученную кодовую комбинацию:
101010011010101010101001100101101010101001101010.
Поскольку в принятом сообщении ни в одном такте нет одинаковых символов, а других ошибок мы обнаружить не можем, то, считая, что их нет, декодируем полученное сообщение по схеме 01 → 0, 10 → 1, и получаем декодированное сообщение:
111011111110100111110111.
