Каков информационный вес одного символа компьютерного алфавита, мощность которого равна 128

Обновлено: 04.07.2024

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

Часто мы представляем набор элементов в компьютерной программе, присваивая каждому элементу уникальный код. Например, стандартная схема кодирования ASCII присваивает каждому символу уникальное восьмибитное значение. Требуется определенное минимальное количество битов, чтобы обеспечить достаточное количество уникальных кодов, чтобы у нас был свой код для каждого символа. Например, требуется \(\left\lceil log\ 128\right\rceil\) или семь битов, чтобы обеспечить 128 уникальных кодов, необходимых для представления 128 символов набора символов ASCII. 1

Требование к битам \(\left \lceil log\ n \right\rceil\) для представления \(n\) уникальных кодовых значений предполагает, что все коды будут одинаковой длины, как и коды ASCII. Такие коды называются кодами фиксированной длины. Если все символы использовались одинаково часто, то схема кодирования с фиксированной длиной является наиболее эффективным методом. Однако вы, вероятно, знаете, что не все символы одинаково часто используются во многих приложениях. Например, различные буквы в англоязычном документе имеют очень разную частоту использования.

Таблица 12.18.1 показывает относительную частоту букв алфавита. Из этой таблицы видно, что буква «Е» встречается примерно в 60 раз чаще, чем буква «Z». В обычном ASCII слова «DEED» и «MUCK» занимают одинаковое количество места (четыре байта). Казалось бы, такие слова, как «DEED», состоящие из относительно распространенных букв, должны занимать меньше места, чем такие слова, как «MUCK», состоящие из относительно необычных букв.

Относительная частота встречаемости 26 букв алфавита в выбранном наборе документов на английском языке. «Частота» представляет собой ожидаемую частоту появления на 1000 букв без учета регистра.

\[\begin\begin \textbf&\textbf&\textbf&\textbf\\ \textrm A & 77 & N & 67\\ \textrm B & 17 & O & 67\\ \textrm C & 32 & P & 20\\ \textrm D & 42 & Q & 5\\ \textrm E &120 & R & 59\\ \textrm F & 24 & S & 67\\ \textrm G & 17 & T & 85\\ \textrm H & 50 & U & 37\\ \textrm I & 76 & V & 12\\ \textrm J & 4 & W & 22\\ \textrm K & 7 & X & 4\ \ \textrm L & 42 & Y & 22\\ \textrm M & 24 & Z & 2\\ \end\end\]

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

Для простоты в этих примерах построения деревьев Хаффмана используется отсортированный список, чтобы упорядочить частичные деревья Хаффмана по частоте. Но реальная реализация будет использовать кучу для реализации приоритетной очереди, определяемой частотами.

12. 18.1.1. Построение деревьев кодирования Хаффмана¶

Кодирование Хаффмана присваивает символам коды таким образом, что длина кода зависит от относительной частоты или веса соответствующего символа. Таким образом, это код переменной длины. Если предполагаемая частота букв соответствует фактической частоте, найденной в закодированном сообщении, то длина этого сообщения обычно будет меньше, чем если бы использовался код фиксированной длины. Код Хаффмана для каждой буквы получается из полного бинарного дерева, называемого деревом кодирования Хаффмана, или просто деревом Хаффмана. Каждый лист дерева Хаффмана соответствует букве, и мы определяем вес листового узла как вес (частоту) связанной с ним буквы. Цель состоит в том, чтобы построить дерево с минимальным весом внешнего пути. Определите взвешенную длину пути листа как его вес, умноженный на его глубину. Двоичное дерево с минимальным весом внешнего пути — это дерево с минимальной суммой взвешенных длин путей для данного набора листьев. Буква с большим весом должна иметь малую глубину, чтобы она меньше всего учитывалась в общей длине пути. В результате другая буква может оказаться глубже в дереве, если она имеет меньший вес.

Процесс построения дерева Хаффмана для \(n\) букв довольно прост.Во-первых, создайте набор из \(n\) начальных деревьев Хаффмана, каждое из которых представляет собой одиночный листовой узел, содержащий одну из букв. Поместите \(n\) частичных деревьев в очередь приоритетов, организованную по весу (частоте). Затем удалите первые два дерева (с наименьшим весом) из очереди приоритетов. Соедините эти два дерева вместе, чтобы создать новое дерево, корнем которого являются два дерева в качестве дочерних, а вес которого равен сумме весов двух деревьев. Поместите это новое дерево обратно в очередь приоритетов. Этот процесс повторяется до тех пор, пока все частичные деревья Хаффмана не будут объединены в одно.

Относительная частота восьми выбранных букв.

\[\begin\begin <|c|cccccccc|>\hline \textrm Letter & C & D & E & K & L & M & U & Z\\ \textrm Frequency & 32 & 42 & 120 & 7 & 42 & 24 & 37 & 2\\ \hline \end\end\]

Следующее слайд-шоу иллюстрирует процесс построения дерева Хаффмана для восьми букв таблицы 12.18.2. 2

Сохранение.
Ошибка сервера
Отправить повторно

Вот реализация узлов дерева Хаффмана.

Эта реализация похожа на типичную иерархию классов для реализации полных двоичных деревьев. Существует абстрактный базовый класс с именем HuffNode и два подкласса с именами LeafNode и IntlNode. Эта реализация отражает тот факт, что листовые и внутренние узлы содержат совершенно разную информацию.

Вот реализация класса дерева Хаффмана.

Вот реализация процесса построения дерева.

buildHuff принимает в качестве входных данных fl минимальную кучу частичных деревьев Хаффмана, которые изначально представляют собой однолистовые узлы, как показано на шаге 1 слайд-шоу выше. Тело функции buildTree состоит в основном из цикла for. На каждой итерации цикла for первые два частичных дерева удаляются из кучи и помещаются в переменные temp1 и temp2. Дерево создается ( temp3 ) таким образом, что левое и правое поддеревья являются temp1 и temp2 соответственно. Наконец, temp3 возвращается в fl .

Кодирование ASCII фактически использует 8 бит на символ. Семь бит используются для представления 128 кодов набора символов ASCII. Восьмой бит используется как бит четности, который можно использовать для проверки наличия ошибки передачи символа.

Присвоение и использование кодов Хаффмана

После того как дерево Хаффмана построено, легко присвоить коды отдельным буквам. Начиная с корня, мы присваиваем каждому ребру дерева значение «0» или «1». «0» присваивается ребрам, соединяющим узел с его левым дочерним элементом, и «1» — ребрам, соединяющим узел с его правым дочерним элементом. Этот процесс иллюстрируется следующим слайд-шоу.

Сохранение.
Ошибка сервера
Отправить повторно

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

Сохранение.
Ошибка сервера
Отправить повторно

Теперь, когда у нас есть код для каждой буквы, кодирование текстового сообщения выполняется путем замены каждой буквы сообщения ее двоичным кодом. Для этой цели можно использовать таблицу поиска.

12. 18.1.2. Декодирование¶

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

Когда мы декодируем символ с помощью дерева кодирования Хаффмана, мы идем по дереву по пути, определяемому битами в строке кода. Каждый бит «0» указывает на левую ветвь, а каждый бит «1» указывает на правую ветвь. В следующем слайд-шоу показан пример декодирования сообщения путем соответствующего обхода дерева.

Сохранение.
Ошибка сервера
Отправить повторно

12. 18.1.3. Насколько эффективно кодирование Хаффмана?¶

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

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

В частном случае частот, показанных в таблице 12.18.1, мы можем определить ожидаемую экономию от кодирования Хаффмана, если фактические частоты закодированного сообщения совпадают с ожидаемыми частотами. Поскольку сумма частот равна 306, а E имеет частоту 120, мы ожидаем, что она появится 120 раз в сообщении, содержащем 306 букв. Фактическое сообщение может соответствовать или не соответствовать этому ожиданию. Буквы D, L и U имеют длину кода, равную трем, и ожидается, что вместе они появятся 121 раз в 306 буквах. Буква C имеет длину кода четыре, и ожидается, что она появится 32 раза в 306 буквах. Буква M имеет кодовую длину пять, и ожидается, что она появится 24 раза в 306 буквах. Наконец, буквы K и Z имеют длину кода, равную шести, и ожидается, что вместе они появятся только 9 раз в 306 буквах. Средняя ожидаемая стоимость символа — это просто сумма стоимости каждого символа ( \(c_i\) ), умноженная на вероятность его появления ( \(p_i\) ), или \(c_1 p_1 + c_2 p_2 + \cdots + c_n p_n.\) Это можно реорганизовать как \(\frac\) , где \(f_i\) - (относительная) частота букв \(i\), а \(f_T\) - общая частота всех букв. Для этого набора частот ожидаемая стоимость одной буквы равна \([(1 х 120) + (3 х 121) + (4 х 32) + (5 х 24) + (6 х 9)] /306 = 785/306 \приблизительно 2,57.\)

Для кода фиксированной длины для этих восьми символов потребуется \(\log 8 = 3\) битов на букву, в отличие от примерно 2,57 битов на букву для кодирования Хаффмана. Таким образом, ожидается, что кодирование Хаффмана позволит сэкономить около 14 % для этого набора букв.

Кодирование по методу Хаффмана для всех символов ASCII должно работать лучше, чем в этом примере. Буквы таблицы 12.18.1 нетипичны тем, что в них слишком много общих букв по сравнению с количеством редких букв. Кодирование Хаффмана для всех 26 букв даст ожидаемую стоимость 4,29 бита на букву. Эквивалентный код фиксированной длины потребовал бы около пяти битов. Это несколько несправедливо по отношению к кодированию с фиксированной длиной, потому что на самом деле есть место для 32 кодов в пяти битах, но только для 26 букв. В более общем плане, кодирование Хаффмана типичного текстового файла сэкономит около 40% по сравнению с кодированием ASCII, если мы взимаем за кодирование ASCII восемь битов на символ. Кодирование Хаффмана для двоичного файла (например, скомпилированного исполняемого файла) будет иметь совершенно другой набор частот распространения и, следовательно, будет иметь другую экономию места. Большинство коммерческих программ сжатия используют две или три схемы кодирования для адаптации к разным типам файлов.

В примере декодирования «DEED» был закодирован 8 битами, что на 33 % меньше двенадцати битов, необходимых для кодирования фиксированной длины. Однако для «MUCK» потребуется 18 бит, больше места, чем требуется для соответствующего кодирования с фиксированной длиной. Проблема в том, что «MUCK» состоит из букв, которые не должны встречаться часто. Если сообщение не соответствует ожидаемой частоте букв, то и длина кодировки не будет такой, как ожидалось.

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

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

Связанные термины:

Скачать в формате PDF

Об этой странице

Системы PMR и транкинговой радиосвязи

46.8.2 Кодовое слово адреса

Первое кодовое слово каждого сообщения является адресным кодовым словом, как показано на рис. 46.12. Бит 1 всегда равен двоичной 1, чтобы отличить слово от кодового слова данных, биты со 2 по 8 включительно определяют личность пользователя, биты с 9 по 48 включительно могут быть назначены для представления адресов и данных, а биты с 49 по 64 включительно являются контрольными битами. В поле данных рекомендуется использовать биты с 9 по 20 для указания идентификатора адресата, биты с 21 по 32 для указания идентификатора адресанта, а биты с 33 по 48 использовать для данных.

< бр />

Рисунок 46.12. Структура кодового слова адреса MPT1317

Усовершенствованное кодирование для оптических коммуникаций

6.2.1 Матрица генератора

Любое кодовое слово x из (n, k) линейного блочного кода может быть представлено как линейная комбинация k< /em> базисные векторы gi (i = 0, 1, …, k − 1) как задано ниже:

(6.1) x = m 0 g 0 + m 1 g 1 + ⋯ + m k - 1 g k - 1 = m g 0 g 1 ⋯ g k - 1 = mG ; грамм знак равно грамм 0 грамм 1 ⋯ грамм k - 1 , м знак равно ( м 0 м 1 ⋯ м k - 1 )

где m — вектор сообщения, а G — порождающая матрица (размерами kxn ), в котором каждая строка представляет собой вектор из кодирующего подпространства.Следовательно, для кодирования вектор сообщения m (m0, m1, …, mk−1) необходимо умножить на порождающую матрицу G, чтобы получить < em>x = mG, где x (x0, x1, …, xn−1) — кодовое слово.

Пример 6.3

Матрицы генератора для повторения (n, 1) кода Grep и (n, n − 1) коды с одинарной проверкой на четность Gpar задаются, соответственно, как

Элементарными операциями над строками в порождающей матрице код может быть преобразован в систематизированную форму.

где Ik — единичная матрица размеров k × k, а P — матрица размеров k × (n − k) со столбцами, обозначающими позиции проверок четности

(6.3) P = P 00 P 01 ⋯ P 0 , n - k - 1 P 10 P 11 ⋯ P 1 , n - k - 1 ⋯ ⋯ ⋯ P k - 1 , 0 P k - 1 , 1 ⋯ P k - 1 , n - k - 1 .

< бр />

Рисунок 6.2. Структура систематического кодового слова.

Поэтому при кодировании вектор сообщения остается неизменным, а элементы вектора проверок на четность b получаются

Во время передачи оптический канал вносит ошибки, так что полученный вектор r может быть записан как r = x + e , где e — вектор ошибок (шаблон) с компонентами элементов, определяемыми

Чтобы определить, является ли полученный вектор r вектором кодового слова, мы вводим понятие матрицы проверки на четность.

Методы кодирования видео с защитой от ошибок

Мохаммед Эбрахим Аль-Муалла, . Дэвид Р. Булл, Видеокодирование для мобильных коммуникаций, 2002 г.

9.6.3.3 Обратимое кодирование переменной длины (RVLC)

Обратимые кодовые слова VLC предназначены для декодирования как в прямом, так и в обратном направлении. Как уже было описано, когда в битовом потоке обнаруживается ошибка, декодер отбрасывает все биты до следующего кодового слова ресинхронизации, где синхронизация восстанавливается, и декодер возобновляет процесс декодирования. Отброшенные биты вполне могут быть правильно приняты, но не могут быть правильно декодированы из-за потери синхронизации. В случае RVLC, когда декодер идентифицирует следующее кодовое слово ресинхронизации, вместо того, чтобы отбрасывать все предыдущие биты, декодер начинает декодирование в обратном направлении, чтобы восстановить и использовать некоторые из этих битов. Это показано на рис. 9.3(b).

Обратимое кодирование переменной длины было принято в самых последних усилиях по стандартизации. Например, модифицированный неограниченный режим вектора движения (модифицированное приложение D) H.263+ использует RVLC для кодирования различий векторов движения, режим секционированных данных (приложение V) H.263++ использует RVLC для кодирования заголовка и информации о движении. , а MPEG-4 использует RVLC для кодирования информации о текстуре.

Расширенные реализации

Хусрев Т. Сенкар , . Али Н. Акансу, в книге «Основы и приложения сокрытия данных», 2004 г.

6.2.7 Реализация и результаты моделирования

Конкретный базис преобразования получается последовательным умножением N ( N − 1 ) 2 ортогональных матриц, все с определителем 1, так что результат является унитарным. Каждая ортогональная матрица получается из единичной матрицы путем введения членов cos θk в (i, i) и (j, j) местоположения вместе с sin θk и –sin θk термины в местах (i, j) и (j, i) чтобы повернуть координатную плоскость (i, j) на заданный угол θk. Углы поворота θk, k = 1, …, L, выбираются путем равномерной выборки 2 π , θ k знак равно ( k - 1 ) 2 π L .

Установив размер сигнала на N и количество сообщений на M, размер кодовых книг, используемых устройством для внедрения, фиксируется на M. em> × N. Сигналы водяных знаков, встроенные в сигнал хоста, генерируются с использованием матрицы преобразования Адамара из-за ее простоты. Матрица преобразования Адамара размером N × N и ее инвертированная версия объединяются в двоичный файл размером 2N × N. ценная матрица. Каждая строка комбинированной матрицы индексируется от 1 до M = 2N, масштабируется на Δ 4 для максимального разделения и назначается сигналу водяного знака Wj, 1 ≤ j ≤ M, такие, что E [ W i TW j ] = 0 , i ≠ j и i ≠ j + N. Сигнал хоста и шум канала представляют собой iid гауссовские векторы с нулевым средним значением, где σ C 2 ≫ P E , σ Z 2 .Перед встраиванием фиксируется допустимое искажение вложения PE, и для рассматриваемых WNR выводятся оптимальные значения параметра вложения Δ. Значения Δ также сообщаются детектору. Однако параметры β и α должным образом настраиваются для каждого встраивания, чтобы обеспечить искажение встраивания PE, и не известны детектору. Моделирование выполняется для различного количества преобразований L и размеров сигнала N путем встраивания и обнаружения случайно выбранных индексов сообщений.

Скрытие нескольких кодовых книг реализовано в схеме типа III на основе пороговой обработки и типов постобработки с компенсацией искажений с использованием как критерия максимальной корреляции, так и критерия минимального расстояния. Внедрение и обнаружение сообщений с использованием до 25 кодовых книг выполняется с учетом размеров кодовых книг 64 × 32, 128 × 64 и 256 × 128 и диапазона WNR от 0,1 до 1. На рисунках 6-23 и 6-24 показана вероятность успешных результатов. получено, соответственно, для L = 1, 3 и L = 1, 4 с различными значениями N, где постобработка является пороговой. Увеличение размера сигнала внедрения N при фиксированном количестве кодовых книг улучшает статистику обнаружения, поскольку нормированная корреляция и среднеквадратичное расстояние дают более надежные результаты при больших размерах сигнала. С другой стороны, рис. 6-25 и 6-26 отображают производительность постобработки с пороговым значением, когда N = 128 и L = 1, 3, 5, 9, 14, 25 с использованием два критерия. Соответствующие результаты для обработки с компенсацией искажений показаны на рис. 6-27 и 6-28 по обоим критериям. Из этих имитаций производительности видно, что метод сокрытия данных с несколькими кодовыми книгами имеет более высокую производительность по сравнению с соответствующим методом с одной кодовой книгой при том же N.

< бр />

Рисунок 6-23. Вероятность успешного выполнения скрытия с тремя кодовыми книгами на основе пороговой обработки и критерия максимальной корреляции для различных размеров сигнала водяного знака N =32, N = 64 и N =128.

< бр />

Рисунок 6-24. Вероятность успешного выполнения для скрытия четырех кодовых книг на основе пороговой обработки и критерия минимального расстояния для различных размеров сигнала водяного знака N =32, N =64 и N =128.

< бр />

Рисунок 6-25. Вероятность успешного выполнения скрытия нескольких кодовых книг на основе порогового типа обработки и критерия максимальной корреляции для L = 1,3,5,9,14,25 и N =128 .

< бр />

Рисунок 6-26. Вероятность успешного выполнения скрытия нескольких кодовых книг на основе порогового типа обработки и критерия минимального расстояния для L = 1,3,5,9,14,25 и N =128 .

< бр />

Рисунок 6-27. Вероятность успешного выполнения скрытия нескольких кодовых книг на основе типа обработки с компенсацией искажения и критерия максимальной корреляции для L = 1,3,5,9,14,25 и N = 128.

Рисунок 6-28. Вероятность успешного выполнения для сокрытия нескольких кодовых книг на основе типа обработки с компенсацией искажения с использованием критерия минимального расстояния для L = 1,3,5,9,14,25 и N = 128.

Вычислительная сложность предлагаемого метода зависит от количества используемых кодовых книг. Внедрение нескольких кодовых книг по сравнению с внедрением одной кодовой книги требует внедрения сигнала водяного знака в преобразования основного сигнала и сравнения на основе результирующих сигналов для выбора основы преобразования. С другой стороны, на детекторе извлечение следует повторять для каждого базиса преобразования. Следовательно, вычислительная сложность увеличивается почти линейно с количеством кодовых книг (см. рис. 6-10).

Принципы обнаружения и исправления ошибок

2.1 Основные понятия

2.1.1 Модель цифровой системы связи

Чтобы обнаруживать или исправлять ошибки в цифровых каналах связи, мы используем методы кодирования с контролем ошибок. На рис. 2.1 представлена ​​концептуальная схема цифровой системы связи с кодированием с защитой от ошибок.


Рис. 2.1 . Модель цифровой системы связи.

На рис. 2.1 передаваемое сообщение представляет собой последовательность двоичных символов длины k, которая обозначается u = (u1< /sub>, u2 ⋯uk), где u i = 0 или 1. Сообщение передается в кодировщик для создания кодового слова . Кодовое слово — это двоичная последовательность длины n (n > k), которая обозначается x = ( x1, x2 ⋯xn< /em>), где xi = 0 или 1. Отображение кодировщика выбрано таким образом, чтобы определенные ошибки могли быть обнаруживаются или исправляются на принимающей стороне. Это сопоставление увеличивает количество символов с k до n. Отношение k/n называется кодовой скоростью и обозначается R.

Существует два типа методов кодирования. Во-первых, это блочное кодирование, при котором каждое кодовое слово генерируется из одного блока из k символов сообщения. Таким образом, блочный кодировщик не сохраняет никакой информации о блоке сообщения после завершения операции кодирования блока. Второй — сверточное кодирование, при котором каждое кодовое слово генерируется из нескольких последовательных блоков сообщений. Как правило, сверточный кодировщик состоит из регистров сдвига для сохранения символов сообщений и логических схем для создания выходных символов.

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

Пусть C = x1, x2, …, xM> — набор всех возможных кодовых слов, сгенерированных кодировщиком, где M = 2 k — количество возможных сообщений. Набор C называется кодом.

Кодовое слово от кодировщика передается по каналу. Канал может быть устройством хранения в некоторых приложениях. Принимающая сторона получает последовательность длины n, y = (y1, y2< /sub> ⋯yn), который называется полученным вектором. декодер оценивает по полученному вектору y переданное кодовое слово x и доставляет оцененное кодовое слово ◯ или, что то же самое, оцененное сообщение û адресату. В некоторых случаях декодер только решает, произошла ли какая-либо ошибка в канале.

Методы декодирования подразделяются на два класса. Один называется декодированием с жестким решением, когда приемник решает, является ли каждый переданный символ 0 или 1, а полученный вектор y является двоичной (0 или 1) последовательностью. Другой — декодирование с мягким решением, когда приемник генерирует некоторую аналоговую информацию о каждом полученном символе, а декодер восстанавливает сообщение из аналогового или квантованного принятого вектора y. (Количество уровней квантования больше 2.)

Если канал бесшумный, полученный вектор y равен переданному кодовому слову x. Но если канал зашумлен, что всегда имеет место, y может отличаться от x. Таким образом, полученный вектор выражается как

где e = (e1, e2 ⋯e< sub>n) представляет эффект шума канала. e называется вектором ошибок. При декодировании с жестким решением e является двоичным вектором, тогда как при декодировании с мягким решением e является аналоговым или многозначным вектором. Чтобы упростить изложение, в этой главе будет обсуждаться только случай декодирования жестких решений, если не указано иное.

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

Это добавление можно выполнить с помощью вентиля исключающее ИЛИ.

Каждый бит в e показывает, произошла ли ошибка в переданном бите. Если произошла ошибка в i-м бите переданного кодового слова, то ei = 1; в противном случае ei = 0.

Пример 2.1

Предположите кодовое слово

передается. Если ошибки произошли в первом и пятом битах кодового слова, вектор ошибки равен

Читайте также: