Курсовая работа по «Основам сбора, передачи и обработки информации»

 

Подсчитаем вероятность  появления двоичных символов в закодированном тексте:

По формуле (3) рассчитаем энтропию источника вторичного ансамбля сообщений B - H(B) (количество символов алфавита n = 2):

Теперь по формуле (6) найдем энтропию источника при кодировании  его первичного ансамбля сообщений A кодом Хаффмана:

.

Энтропия источника  первичного ансамбля сообщений A:

.

Следовательно:

≈ .

Вывод: из двух пунктов доказательства следует, что код Хаффмана является оптимальным.

 

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

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

Краткие теоретические сведения

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

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

Минимальное кодовое расстояние этого  кода d_min = 1, поэтому код с проверкой на четность обнаруживает все одиночные ошибки, а кроме того, все случаи нечетного числа ошибок (3, 5 и т. д.). При одновременном возникновении двух или любого другого четного числа ошибок код с проверкой четности не обнаруживает ошибок.

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

Кодирование

Кодовая комбинация, которую  необходимо закодировать:

111011111110100111110111.

Количество единиц в слове – 19, следовательно, проверочный разряд равен 1, поскольку тогда количество единиц в закодированной кодовой комбинации будет четное.

Закодированная кодовая  комбинация:

111011111110100111110111 1.

Поскольку количество избыточных символов – 1, а длина закодированной кодовой комбинации – 25, то избыточность будет равняться (см. формулу (1)):

.

Декодирование

Декодируем полученную кодовую комбинацию:

111011111110100111110111 1.

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

111011111110100111110111.

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

Краткие теоретические сведения

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

При контроле по нечетности контролируется полное пропадание информации, поскольку  кодовое слово, состоящее из 0, относится  к запрещенным.

Кодирование

Кодовая комбинация, которую  необходимо закодировать:

111011111110100111110111.

Количество единиц в слове – 19, следовательно, проверочный разряд равен 0, поскольку тогда количество единиц в закодированной кодовой комбинации будет нечетное.

Закодированная кодовая комбинация:

111011111110100111110111 0.

Аналогично коду с  проверкой на четность избыточность составляет:

.

Декодирование

Декодируем полученную кодовую комбинацию:

111011111110100111110111 0.

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

111011111110100111110111.

4.3. Инверсный код

Краткие теоретические сведения

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

Для обнаружения ошибок в кодовом  слове, состоящем из n = k + r символов производится две операции:

1. суммируются единицы, содержащиеся в первых k символах кодового слова.
2. если число единиц четное, r последующих символов сравниваются попарно с первыми k символами; если число единиц в первых символах нечетное, последующие символы перед сравниванием инвертируются.

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

Ошибка в кодовом слове не обнаруживается, если одновременно искажается четное число символов в исходном слове и соответствующие им кодовые символы в последовательности повторяемых r символов.

Кодирование

Кодовая комбинация, которую необходимо закодировать:

111011111110100111110111.

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

Закодированная кодовая комбинация:

111011111110100111110111 000100000001011000001000.

Поскольку количество избыточных символов – 24, а длина закодированной кодовой комбинации – 48, то избыточность будет равняться (см. формулу (1)):

.

Декодирование

Декодируем полученную кодовую комбинацию:

111011111110100111110111 000100000001011000001000.

Количество единиц, содержащихся в первых 24 символах кодового слова – 19, то есть нечетное число. Значит, 24 последующих символов сравниваем попарно с инвертированным первыми 24 символами. Все символы попарно совпадают. Поскольку данный код не позволяет обнаружить ошибку, если одновременно искажается четное число символов в исходном слове и соответствующие им кодовые символы в последовательности повторяемых r символов, то, считая, что таких ошибок нет, просто отбрасываем повторяемые символы и получаем декодированное сообщение:

111011111110100111110111.

 

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

Краткие теоретические сведения

Кодирование корреляционным кодом производится по схеме превращения: 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.

 

4.5. Код Бергера

Краткие теоретические сведения

Коды Бергера относятся  к разряду несистематических  кодов. Существует несколько вариантов  построения кодов Бергера. В наиболее простом варианте кодирование происходит следующим образом: в информационной части кода подсчитывается число  единиц, после чего формируются проверочные разряды, представляющие инвертированную запись этого числа в двоичной форме. Таким образом, число проверочных разрядов R равно наименьшему целому числу, превышающему log₂(k), то есть R >= log₂(k).

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

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

Кодирование

Кодовая комбинация, которую  необходимо закодировать:

111011111110100111110111.

Количество единиц в  слове – 19, в двоичном представлении – 10011. Инвертируем это число – 01100 – и добавляем его к исходному слову. Получаем закодированную кодовую комбинацию:

111011111110100111110111 01100.

Поскольку количество избыточных символов – 5, а длина закодированной кодовой комбинации – 29, то избыточность будет равняться (см. формулу (1)):

.

Декодирование

Декодируем полученную кодовую комбинацию:

111011111110100111110111 01100.

Зная, что количество информационных символов – 24, подсчитываем количество единиц в информационном блоке – их 19. Берем 5 избыточных символов – 01100 – и инвертируем избыточный блок – 10011. Переводим полученное число в десятичный вид – 19. Оно совпадает с количеством единиц в информационном блоке. Это означает, что ошибок, которые мы можем обнаружить, нет. Значит, отбрасываем проверочные символы и получаем декодированное сообщение:

111011111110100111110111.

4.6. Код на одно сочетание

Краткие теоретические сведения

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

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

Кодирование

Кодовая комбинация, которую  необходимо закодировать:

111011111110100111110111.

Закодируем данное сообщение, разделив его на 3 кодовых слова и кодируя каждое отдельно кодом с постоянным весом 8. Следовательно, длина каждого закодированного слова будет составлять 16 символов – 8 информационных и 8 избыточных.

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

1) 1110111110000000,   2) 1110100111100000,   3) 1111011110000000.

Собираем эти три закодированных слова в одно сообщение, и получаем следующую закодированную кодовую комбинацию:

111011111000000011101001111000001111011110000000.

Поскольку количество избыточных символов в каждом закодированном слове  – 8, а длина закодированного слова  – 16, то избыточность будет равняться (см. формулу (1)):

.

Декодирование

Декодируем полученную кодовую комбинацию:

111011111000000011101001111000001111011110000000.

Зная, что полученное сообщение  состоит из трех отдельно закодированных кодом с постоянным весом 8 слов, декодируем отдельно каждое слово длиной в 16 символов. Поскольку вес всех закодированных кодовых слов равен 8, то ошибок, которые мы можем обнаружить, нет. Зная, что 8 избыточных символов находятся в конце закодированного слова, отбрасываем их и получаем три декодированных слова:

1) 11101111,   2) 11101001,   3) 11110111.

Собираем эти три декодированных слова в одно сообщение, и получаем следующую декодированную кодовую  комбинацию:

111011111110100111110111.

 

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

Краткие теоретические сведения

Код с количеством единиц, кратным трем можно получить двумя способами:

1. путем добавления к слов<span class="dash041e_0431_044b_0447_043d_044b_0439__