Как найти минимальную длина двоичного кода

Навигация Кодирование и декодирование информации

Кодирование и декодирование информации Задача 1. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–10, Б–001, В–0001, Г–110, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.   1) для буквы Г – 11  3) для буквы В – 000  2) это невозможно  4) для буквы Б – 00 Решение: Построим кодовое дерево,в котором от каждого узла отходит две ветки, соответствующие выбору следующей цифры кода. Код букв получается как последовательность чисел на рёбрах, составляющих путь от корня до данной буквы: Код однозначно декодируется, если при движении от корня к любой букве в середине пути не встречается других букв (выполняется условие Фано); Проверим варианты ответа: однозначность декодирования не нарушается только при переносе буквы В в узел 000 (хотя очевидно, что можно было бы перенести букву В в узел 01, но такого варианта ответа нет). Следовательно, правильный ответ указан под номером 3. Ответ: 3 Задача 2. Для пяти букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трёх). Эти коды приведены в таблице:  А  В  С  D  E  000 11  01  001  10 Какое из приведенных ниже сообщений, записанных в данной кодировке, может быть корректно декодировано (т.е. не содержит ошибки)?  1) 11010001001001110  3) 11000001001111010  2) 110000000011011110  4) 11000000101111010 Решение: Представленный код является префиксным,поэтому сообщение должно однозначно декодироваться. Декодируем ответы, выделяя коды символов с начала строки:  1) 11 01 000 10 01 001 11 0  2) 11 000 000 001 10 11 11 0  3) 11 000 001 001 11 10 10  4) 11 000 000 10 11 11 01 0 Во всех строках, кроме третьей, в результате декодирования появилось кодовое слово 0, которого нет в таблице. Следовательно, только третья строка может быть корректно декодирована Ответ: 3 Справочные материалы Знаковая система состоит из упорядоченного набора знаков (символов), который называется алфавитом. Полное количество символов алфавита называется мощностью алфавита. Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки с помощью символов некого алфавита. При этом каждый символ исходного алфавита (мощности N) при кодировании представляется последовательностью символов кодового алфавита (мощности M), которая называется кодовым словом.  Иногда кодовое слово называют кратко кодом. Двоичное кодирование — это кодирование с помощью алфавита из двух знаков. Если кодирование  осуществляется кодовыми словами переменной длины, такой код называется неравномерным. Декодирование — это восстановление сообщения из последовательности кодов. Закодированное неравномерным кодом сообщение можно однозначно декодировать с начала, если выполняется прямое условие Фано: никакое кодовое слово не является началом другого кодового слова. Закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является концом другого кодового слова. Префиксный код — это неравномерный код, для которого выполняется прямое условие Фано. Сообщения, закодированные префиксным кодом, можно декодировать «на лету», не дожидаясь получения всего сообщения целиком. Префиксные коды используются для кодирования аудио- и видеофайлов, поэтому можно слушать музыку или смотреть видео до того, как файл загрузится целиком. Если кодирование  осуществляется кодовыми словами одинаковой длины, такой код называется равномерным. При таком кодировании нет необходимости вводить символ-разделитель, но сообщение, чаще всего, становится длиннее, чем при использовании неравномерных кодов. Если мощность кодового алфавита равна M, а длина кода — l,  можно составить N = Ml различных кодовых слов. Пример 1. Какой должна быть минимальная длина равномерного двоичного кода,если требуется составить 18 различных кодовых комбинаций? Решение: Количество комбинаций можно считать символами исходного алфавита, тогда мощность исходного алфавита N=18. Мощность двоичного кодового алфавита M=2. Из формулы N =2l  найдем длину двоичного кода l = log2N =log218. Округлим полученный результат до ближайшего целого. Получим  l = 5. Или: используя таблицу степеней числа 2, найдем длину двоичного кода l, такую, что 2l≥18. Т.к. 25=32≥18, то l = 5. Ответ: 5. Пример 2. Два сторожевых отряда, расположенных на большом расстоянии друг от друга, условились передавать друг другу сообщения с помощью сигнальных ракет белого, красного и зеленого цвета. Сколько различных сообщений можно передать, запустить ровно 5 ракет (ракет каждого вида неограниченное количество)? Решение: Мощность кодового алфавита M=3 (используются ракеты трёх цветов). Длина кодового слова l=5 (ровно 5 ракет). Из формулы N =Ml  найдем количество комбинаций N =35 = 243 Эту задачу можно решить простыми рассуждениями. Так как имеем неограниченное количество ракет трёх видов, то каждую следующую ракету в последовательности из пяти ракет можно выбрать тремя способами. Получаем 3·3·3·3·3=243. Ответ: 243.

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

Ну да ладно, вычислим, сколько информации содержит 1 символ при мощности алфавита = 33:

33 = 2ˣ => минимальный x = 6

Значит один символ будет нести 6 бит информации, то есть длина двоичного кода для записи одного символа равна 6.

Если мы умножим 6 на количество символов, то получим количество информации, требуемое для записи 33 букв, т.е.:

6*33 = 198 бит

Ответ: Длина двоичного кода одной буквы равна 6, а 33 букв — 198.

Задача: 2

Вася и Петя передают друг другу сообщения,
используя синий, красный и зелёный фонарики. Это
они делают, включая по одному фонарику на
одинаковое короткое время в некоторой
последовательности. Количество вспышек в одном
сообщении — 3 или 4, между сообщениями — паузы.
Сколько различных сообщений могут передавать
мальчики?

Решение:
1.


3- мощность языка
вспышки 3 и 4 (N 3,4)
3*4=12
3*3=9
12*9=108


2.


3*3*3 = 27
3*3*3*3 = 81
27+81=108


Ответ: 108

Задача: 3


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

фигуры?


Решение:


8*8 = 64 =>
=>2^6 = 64 =>
=>6 битов 

Ответ: 6 бит.


Задача: 4

 Для кодирования значений температуры воздуха
(целое число в интервале от –50 до 40) используется
двоичный код. Какова минимальная длина двоичного
кода?

Решение:


от -50 до 40 = 91 


2^6  < 91 < 2^7 => 7 битов


2^6 = 64

2^7 = 128


Ответ: 128 — минимальная длина двоичного
кода и 7 битов 


Задача: 5

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


Решение:
Q = 6
2^4 < 6 <= 2^3
1 сигнал — 3 бита
100 сигналов — 300 байта


Ответ:  300 байта

Характеристика задания

1. Тип ответа: числовой.

2. Структура содержания задания: дана текстовая задача с вариантами кодов, либо в задаче записано, какой алфавит нужно закодировать.

3. Уровень сложности: базовый.

4. Примерное время выполнения: (2) минуты.

5. Количество баллов: (1).

6. Требуется специальное программное обеспечение: нет.

7. Задание проверяет умение кодировать и декодировать информацию.

Пример задания из демоверсии ЕГЭ (2023).

По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий прямому условию Фано, согласно которому никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Н — (1111), З — (110). Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

Для решения задания построим двоичное дерево.

Алгоритм решения

1. Рассмотрим предложенное слово: если буквы повторяются, то для их кода выбирается код минимальной длины.
2. Внимательно прочитаем условие задания: в предложенном задании написано: «По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч», следовательно, кроме букв А, З, К, Н, Ч, букв в алфавите больше нет. В некоторых заданиях можно увидеть такую запись: «в сообщении могут встречаться и другие буквы, кроме тех, которых входят в передаваемое слово», следовательно, при построении дерева нужно учитывать, что букв может быть больше, и оставлять для этого хотя бы одну свободную «ветку» двоичного дерева.
3. Построим двоичное дерево, соблюдая условие, что код должен быть минимальной длины.

Учитывая предложенный алгоритм, решим задание из ЕГЭ (2023).

1. Дано слово КАЗАЧКА, буква «А» встречается три раза, буква «К» встречается два раза, поэтому при кодировании букве «А» должен соответствовать самый минимальный код, вторым по длине будет код для буквы «К».
2. В задании сказано, что кроме букв «А, З, К, Н, Ч» больше букв в алфавите нет, следовательно, можно построить дерево, не оставляя свободную «ветку».
3. Учитывая всё вышеизложенное, строим дерево.

Рис. (1). Построение двоичного дерева

Сделаем анализ двоичного дерева и увидим, что:

буква «А» получила код «(0)», длина кода — «(1)»,

«К» получила код «(10)», длина кода — «(2)»,

«З» получила код «(110)», длина кода — «(3)»,

«Ч» получила код «(1110)», длина кода — «(4)».

Отвечаем на вопрос «Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА».

КАЗАЧКА (=) (2+1+3+1+4+2+1=14).

Правильный ответ: (14).

Рассмотрим задание Демоверсии ЕГЭ (2022).

Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв Л, М, Н использовали соответственно кодовые слова (00), (01), (11). Для двух оставшихся букв П и Р кодовые слова неизвестны. Укажи кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, укажи код с наименьшим числовым значением.

Алгоритм решения

1. Для кодирования используют ТОЛЬКО буквы Л, М, Н, П, Р. Минимальный код для буквы «П» (Укажи кратчайшее возможное кодовое слово для буквы П) в данном случае не минимальной длины, а минимальный по коду; если сравнить код «(101)» и «(110)», то минимальным окажется «(101)».
2. Слово не дано, пропускаем шаг.
3. Строим двоичное дерево.

(1) шаг: строим дерево по известным кодам.

Рис. (2). Двоичное дерево для известных кодов

Рис. (3). Кодирование остальных букв

Эффективное кодирование

4.2.12. (нов)

Источник сообщений выдает 9 различных
символов с вероятностями их появления:

Символ	a1	a1	a4	a5	a6	a7	a8	a9	a10
pi	0.2	0.15	0.15	0.12	0.1	0.1	0.08	0.06	0.04

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

Решение. Кодирование по методу
Хаффмена состоит из следующих пунктов:

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

2. выбирают два символа с наименьшими
   вероятностями и первому (верхнему) из
   них в качестве первого числа двоичного
   кода приписывают «1», а второму — символ
   «0»;

3. выбранные символы объединяют в
   «промежуточный» символ с вероятностью
   равной сумме вероятностей выбранных
   символов;

4. в ансамбле оставшихся символов (вместе
   с «промежуточным», учитывая его суммарную
   вероятность) вновь выбирают два символа
   с наименьшими вероятностями и объединяют
   их в «промежуточный» символ (повторяют
   пп.2 и 3);

5. эту процедуру повторяют до тех пор,
   пока не будет исчерпан весь алфавит.

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

Кодирование
по методу Хаффмена.

Символ	рi	Граф кода Хаффмена	Код
a1 а2 а3 а4 а5 а6 а7 а8 а9	0,2 0,15 0,15 0,12 0,1 0.1 0,08 0,06 0,04		11 001 011 010 101 100 0001 00001 00000

Средняя длина кодовой комбинации данного
кода
.

Минимальная длина кодовой комбинации
равномерного кода, которым можно
закодировать данный алфавит:
.

Таким образом, код Хаффмена короче
равномерного кода на 23%.

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

.

Средняя длина кодовой комбинации кода
Хаффмена отличается от средней длины
оптимального кода на (3,08-3,04)/3,04*100%=1,32%,
что позволяет считать код Хаффмена
близким к оптимальному.

4.2. Закодировать двоичным кодом
Шеннона-Фано ансамбль сообщений {a_i},
i=1,2,…8, если вероятности
символов имеют следующие значения:
Р(а₁)=Р(а₂)=1/4;
P(a₃)=P(a₄)=1/8;
P(a₅)=P(a₆)=P(a₇)=P(a₈)=1/16.
Найти среднее число разрядов в кодовой
комбинации. Показать, что такой код
близок к оптимальному.

Решение. Кодирование по методу
Шеннона-Фано состоит из следующих
пунктов:

1. все символы записываются в порядке
   убывания их вероятностей;

2. вся совокупность символов разбивается
   на две примерно равновероятные группы;

3. всем символам верхней группы приписывается
   первый кодовый символ 1; символам нижней
   группы- кодовый символ 0;

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

5. эта процедура повторяется до тех пор,
   пока в каждой подгруппе не останется
   по одной букве;

Процесс кодирования представлен в
таблице.

Кодирование по методу Шеннона-Фано.

Символ	pi	Разбиение	Код.
а1 а2 а3 а4 а5 а6 а7 а8	1/4 1/4 1/8 1/8 1/16 1/16 1/16 1/16					11 10 011 010 0011 0010 0001 0000

Средняя длина кодовой комбинации:
.

При оптимальном двоичном кодировании:
;
т. е. код Шеннона-Фано оптимален для
данного случая.

При использовании равномерного двоичного
кода, его длина для 8 символов составит
.
Таким образом, полученный код Шеннона-Фано
короче равномерного на 8.33%.

Помехоустойчивое кодирование.

4.1.2.

Дискретный источник выдает сообщения
a_i
из ансамбля A={a_i}
с объемом K=10. Какое
минимальное число разрядов должны иметь
кодовые комбинации равномерного
двоичного кода, которым кодируются
данные сообщения. Записать все кодовые
комбинации.

Найти теоретически возможный минимум
для средней длины кодовой комбинации
эффективного кода, которым кодируются
данные сообщения, если энтропия источника
H(A)=2.3
бит/сообщ.

Решение: Число разрядов кодовых
комбинаций равномерного двоичного кода
находится из условия n_рав=log10=3.32.
Так как это число не может быть дробным,
его следует округлить до целых в большую
сторону. Таким образом n_рав=4.
Округление до 3 недопустимо, т.к. при
этом число кодовых комбинаций N=2³=8
будет меньше размера алфавита источника.

Задача эффективного кодирования —
устранение избыточности источника
путем уменьшения средней длины кодовой
комбинации. Для теоретически наилучшего
эффективного кода избыточность будет
равна нулю, но при этом каждый символ
такого кода будет нести максимально
возможное количество информации I_max.
Для двоичного кода I_max=log2=1
бит. Таким образом, чтобы передать 2.3
бита информации (H(A))
необходимо в среднем 2.3 символа. Поэтому
n_minср=H(A)=2.3.

4.1.3.

Ансамбль дискретных символов {a_i}
с объёмом К=32 имеет энтропию H(A)=2
бит/символ. Какое избыточное количество
символов кода по сравнению с оптимальным
кодом приходится тратить на один символ
источника, если используется равномерный
двоичный код.

Указание к решению: Необходимо
определить длину равномерного двоичного
кода n_равн по объёму
алфавита. Длина оптимального кода n_опт
— это минимально возможная средняя длина
кода, пригодного для передачи сообщений
источника с заданной энтропией.

4.1.4.

Аналоговый сигнал путем дискретизации
во времени и квантования по уровню
превращается в импульсную последовательность
с числом уровней К=128. Найти длину кодовой
комбинации. Найти избыточность кода,
если число разрядов кода увеличить на
3.

Решение: Если длина кодовой комбинации
n, то двоичным кодом можно
закодировать K=2ⁿ
сообщений. Отсюда n=log₂K=7.
Если число разрядов кода увеличить на
3, то в коде будет 7 разрядов, несущих
полезную информацию и 3 избыточных
разряда. Поэтому избыточность кода
будет равна: =1-7/10=0.3.

4.1.4а.

Алфавит источника объёмом К=256 кодируется
15-разрядным двоичным кодом. Найти
избыточность кода, а также число
информационных и избыточных разрядов.

5.1.5. (нов)

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

Решение: Обозначим обнаруживаемые
ошибки — О_обн; исправляемые ошибки
— О_исп; все возможные ошибки — О.
Нам необходимо найти О_обн/О и
О_исп/О. Найдем сначала количество
всех возможных ошибок. Если в коде k
инф. символов, то таким кодом можно
закодировать К=2^k
сообщений. Таким образом, в канал связи
передаются К кодовых комбинаций. Назовем
их разрешенными и их число обозначим:
N_p. На
рис. 1 они показаны точками b_1p,
b_2p
и т.д. В результате воздействия шума на
передаваемые кодовые комбинации (N_р),
они могут быть искажены, и тогда будет
принята любая кодовая комбинация из
числа N=2ⁿ.
Комбинации кода из числа N
не входящие в N_р
называют запрещенными комбинациями:
N_з=N-N_p.
Получение приемником такой комбинации
говорит о том, что ошибка произошла. На
рис. 1 они показаны точками b_зап.

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

Рис 1. К оценке
обнаруживающей а) и исправляющей б)
способности кода. b_1р;
b_2р
— разрешенные кодовые комбинации; b_зап
— запрещенные.

Столько же ошибок может дать и любая
другая кодовая комбинация из числа
разрешенных. Поэтому общее число
возможных ошибок О=N_p(N-1).

При получении кодовой комбинации из
числа N_з, ошибка
будет обнаружена, т.к. мы заранее знаем,
что такая комбинация не может быть
передана. Поэтому О_обн=N_p*N_з=N_p(N-N_p).

Тогда получим:

Рис.1б. объясняет принцип исправления
ошибок: любая полученная b_зап
исправляется к ближайшей b_iр.
Поэтому, если была передана, например,
b_1р, то верно
исправляться будут лишь ближайшие к
ней b_зап (при
d<d_min/2).
Таким образом, общее число верно
исправленных ошибок составит N_з.

Таким образом, получим:

4.2.2.

Число разрядов кодовой комбинации
n=125; число информационных
символов k=100. Вероятность
ошибочной регистрации одного кодового
символа — р₀=0.1. Минимальное кодовое
расстояние — d_min=6.
Найти избыточность кода и вероятность
ошибочного декодирования всей кодовой
комбинации.

Решение:

Избыточность кода: =1-k/n=1-100/125=1/5=0.2.

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

В нашей задаче q_и=d_min/2-1=6/2-1=2;
q_o=d_min-1=5.
Поэтому вероятность ошибочного
декодирования равна суммарной вероятности
ошибки кратности 4 и 5:

Здесь 1-р₀ — вероятность правильной
регистрации кодового символа; С_n^q
— количество комбинаций из n
по q, т.е. количество всех
вариантов ошибки кратностью q
в n-разрядной кодовой
комбинации.

4.2.2а.

Найти вероятность правильного
декодирования кодовой комбинации при
n=125; p=0.1;
d_min=6.

4.2.2 б. (5.1.12 нов)

Определить d_min
для кода, обнаруживающего пятикратную
и исправляющего тройную ошибку.

Линейный двоичный блочный код

4.2.4.

Линейный двоичный блочный код,
предназначенный для кодирования восьми
сообщений содержит кодовые комбинации:

b₁=00000; b₂=10011;
b₃=01010; b₄=11001;
b₅=00101; b₆=10110;
b₇=01111; b₈=11100.

Является ли данный код линейным? Найти
избыточность кода и d_min.

Решение: Свойство линейности кода
означает, что при сложении любых двух
комбинаций кода должна получиться
комбинация этого же кода. Сложение здесь
осуществляется поразрядно по модулю 2
(логическая операция «ИСКЛЮЧАЮЩЕЕ
ИЛИ»):

Например, b₂b₃=11001=
b₄.

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

Определим избыточность кода. Длина
кодовых комбинаций n=5, а
для передачи 8 сообщений необходимо
минимум 3 разряда, т.к. n_min=log(K),
где K=8. Поэтому избыточность
кода:

=1-n_min/n=1-3/5=0.4.

Минимальное кодовое расстояние d_min
определяется как число разрядов, которыми
2 кодовые комбинации отличаются друг
от друга. Для данного кода d_min=3.
Проверьте это.

5.2.4. (нов)

Построить линейный код (7;4) по заданной
производящей матрице

Решение: Запись «код (7;4)» означает,
что длина кодовой комбинации этого кода
n=7, а количество информационных
символов n_и=4.
Построить код означает, что к 4-м
информационным символам надо добавить
с помощью матрицы 3 проверочных символа.
Всего с помощью такого кода можно
передать 2^nи
=16 сообщений кодовыми комбинациями от
«0000» до «1111».

Возьмем, например, комбинацию 1010 и
добавим к ней 3 проверочных символа. Эта
исходная комбинация умножается
(логическое «И») как матрица-строка на
матрицу . Каждый
столбец матрицы 
служит для создания одного проверочного
символа.

Результаты поразрядного умножения 1010
на первый столбец:

11=1; 01=0;
11=1; 00=0.

Полученные 4 числа надо сложить по модулю
2 (логическое «ИСКЛЮЧАЮЩЕЕ ИЛИ»):

1010=0

Полученный результат и есть первый
проверочный символ.

Умножение 1010 на второй столбец: 11=1;
01=0; 10=0;
01=0.

Сложение: 1000=1.

Умножение 1010 на третий столбец: 11=1;
00=0; 11=1;
01=0.

Сложение: 1010=0.

Таким образом, для исходной комбинации
1010 мы получили помехоустойчивый код
(7;4) — 1010010

Общая формула для определения проверочных
символы b_пр:

,
где k — количество
информационных символов; r
— количество проверочных символов;
i=k+1,k+2,…k+r;
 —
операция «И», а суммирование осуществляется
по модулю 2.

5.2.4.а

Построить линейный код (7;4) по производящей
матрице задачи 5.2.4. для любых шести
исходных (4 разрядных) кодовых комбинаций.

5.2.6. (нов)

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

Решение: Синдром — это код, количество
разрядов в котором совпадает с количеством
проверочных символов. Если синдром
нулевой (с=000), то поступивший с выхода
канала код верен. Если ходя бы один
разряд синдрома не равен нулю, то в
принятом коде есть ошибка, причем вид
синдрома (количество и порядок единиц
в нем) указывает на разряд, в котором
ошибка произошла.

Пусть был передан код 1010010 (см. задачу
5.2.4.) и, в результате действия шумов в
канале, произошла ошибка в первом
разряде. Таким образом, мы получим код:
0010010. Вычислим для него синдром. Для
этого сначала вычисляются т.н. контрольные
символы. Они вычисляются точно так же,
как и проверочные символы (см. задачу
5.2.4.). Для вычисления берем первые 4
символа поступившего кода («0010») и
матрицу .

Первый контрольный символ: 01011100=1.

Второй контрольный символ: 01011001=0.

Третий контрольный символ: 01001101=1.

Затем необходимо сложить по модулю 2
полученные контрольные символы и
проверочные символы пришедшего кода:

10=1; 01=1;10=1;

Результат сложения и есть синдром.

Таким образом, c=(111). Синдром
ненулевой, значит ошибка есть, а вид
синдрома указывает на то, что она
произошла в 1-м разряде.

5.2.6.б

Построить синдромы для одиночных ошибок
во всех разрядах кода (7;4) из задачи
5.2.4. Показать, что при правильном приеме
кодовой комбинации будет нулевой
синдром.

5.2.12.

Определить, какие из приведенных кодовых
комбинаций содержат одиночную ошибку:

1100111 0110101 0011010 0010110

1000100 1011011 0010101 0110010

1100100 0110101 1001010 0011011

Код построен по производящей матрице:

Циклические коды:

5.3.2.

Первые три комбинации циклического
кода имеют вид: 100001101, 110000110, 011000011.
Построить остальные комбинации этого
кода и порождающий полином кода.
Представить в виде многочленов все
кодовые комбинации.

Решение: Как видно из первых трех
комбинаций, они получены с помощью
циклического сдвига вправо:

b₁=100001101

b₂=110000110

b₃=011000011

Продолжая сдвиг вправо, получим:

b₄=101100001

b₅=110110000

b₆=011011000

b₇=001101100

b₈=000110110

b₉=000011011

Далее циклический сдвиг опять приводит
к комбинации b₁.

Код длиной n можно
представить в виде полинома n-1степени:

b(x)=a₀+a₁x+a₂x²+…+a_n-1x^n-1,

где x — формальная переменная,
степень которой указывает на разряды
кодовой комбинации (мл. разряд — нулевая
степень, старший — n-1
степень); коэффициенты a
— принимают значения 0 или 1, согласно
значениям разрядов кода. (x)

Например, согласно формуле, b₁(x)=x⁸+x³+x²+1;
b₂(x)=x⁸+x⁷+x²+x¹;
и т.д.

Порождающий полином — это многочлен
наименьшей степени. В нашем случае это
b₉(x)=
x⁴+x³+x¹+1.
Порождающий полином обозначается g(x)
и все остальные коды получаются из него.
Например, b₈(x)=g(x)*x;
b₇(x)=g(x)*x²;
и т.д. Проверьте это.

Если в результате такого умножения мы
получим x^s,
где s>n-1,
тогда вместо s надо
поставить степень r=s-n.
Например, g(x)*x⁶=x¹⁰+x⁹+x⁷+x⁶=
x+1+ x⁷+x⁶=b₃.
Это правило реализует цикличность при
сдвиге (т.е., старший разряд помещается
на место младшего).

5.3.8. (нов)

Какие комбинации циклического кода
(7;4), заданного порождающим полиномом
g(x)=1+x²+x³,
содержат ошибку: 1001000, 1111001, 0100101, 1111011,
0010111, 0011111, 0100011, 1010001.

Решение: При анализе циклических
кодов, каждая кодовая комбинация,
поступившая с выхода канала, делится
на порождающий полином. Если остаток
от деления будет 0, то ошибки нет. При
делении вместо операции вычитания
используется «ИСКЛЮЧАЮЩЕЕ ИЛИ».

Например, (g(x)=b₁(x)=0001101)

Остаток от деления равен нулю, следовательно
кодовая комбинация верна.

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

5.3.8.б

Какие комбинации циклического кода
(7;4), заданного порождающим полиномом
g(x)=1+x+x³
содержат ошибку: 0001101, 0011110, 1001101, 1000101,
1100110, 0100011, 1010100, 1100010.

Код с постоянным весом

4.2.12.

Вероятность ошибочного приема
элементарного символа кодовой комбинации
p₀=10^-2. Чему
будет равна вероятность необнаруженной
ошибки при использовании кода с постоянным
весом (3/4).

Решение: Код с постоянным весом
(3/4) содержит в себе любые кодовые
комбинации с тремя единицами и четырьмя
нулями. Если соотношение нулей и единиц
нарушено, то произошла ошибка и такая
кодовая комбинация считается запрещенной.
Отсюда следует, что необнаруженными
будут ошибки, которые не меняют соотношение
нулей и единиц в коде, например, двойная
ошибка — «1» переходит в «0» и «0» в «1».

Вероятность такой ошибки определится
следующим образом. Для трех единиц кода
имеем: две единицы верны и одна (например,
первая) перешла в «0». Вероятность этого
события: p₀*(1-p₀
)*(1-p₀). Вероятность
же перехода любой единицы в «0» будет
определяться количеством комбинаций
из 3 по 1:

; вообще: .

Поэтому: P_(10)=
C¹₃*p₀*(1-p₀
)*(1-p₀).

Аналогично, вероятность перехода любого
из четырех нулей в единицу определится:
P_(01)=
C¹₄*p₀*(1-p₀
)³

Таким образом вероятность двойной
ошибки 10 и 01
составит:

P₍₂₎= C¹₃*p₀*(1-p₀)²
*C¹₄*p₀*(1-p₀)³=3*0.01*0.99²*4*0.01*0.99³=0.001141

Также будет не обнаружена ошибка
кратностью 4 — переход двух единиц в «0»
и двух нулей в «1»:

P₍₄₎= C²₃*p₀²*(1-p₀)
*C²₄*p₀²*(1-p₀)²=3*0.01²*0.99*6*0.01²*0.99²=1.74*10^-7

Ошибка кратностью 6: переход трех единиц
в «0» и трех нулей в «1»:

P₍₆₎= p₀³
*C³₄*p₀³*(1-p₀)
=0.01³*4*0.01³*0.99=3.96*10^-12.

Вероятность необнаруженной ошибки:
P_Н.О.=
P₍₂₎+P₍₄₎+P₍₆₎

Итак: P_Н.О.P₍₂₎=
0.001141

5.4.7.(нов)

Решить задачу 4.2.12. для кодов (4/5); (3/8);
(4/7); (5/6). Вероятность ошибочного приема
элементарного символа кодовой комбинации
p₀=0.1.

Эквивалентная вероятность ошибки

4.3.3.

Найти эквивалентную вероятность ошибки
р_э для линейного кода (7,4) с d_min=3,
если вероятность ошибки в доном символе
р=0.1. Определить выигрыш по р_э при
переходе от примитивного к помехоустойчивому
кодированию.

Решение: Так как d_min=3,
то обнаруживающая способность данного
кода q_o=d_min-1=2;
а исправляющая способность — q_и=(d_min-1)/2=1.
Поэтому код будет декодирован правильно,
если все его символы приняты правильно,
или один из 7 символов принят с ошибкой.
Вероятность правильного декодирования
Р_ПД:

=0.85

Пусть безызбыточный код (4,4) имеет такую
же Р_ПД. Вычислим допустимую при
этом вероятность ошибки в одном его
символе. Это и будет р_э. Для
безызбыточныго кода правильное
декодирование возможно лишь в случае
верного приема всех его символов.
Поэтому: Р_ПД=0.85=(1-р_э)⁴.
Откуда

р_э=1-0.85^1/4=0,04.

Выигрыш по вероятности ошибки в одном
символе при переходе от примитивного
к помехоустойчивому коду составит:

g=p/p_э=2.5.

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

ПЕРЕДАЧА ДИСКРЕТНЫХ СООБЩЕНИЙ

Критерии оптимального приема

5.1.1.

По каналу связи передаются двоичные
символы b₁ и b₂
с вероятностями P(b₁)=0.6;
P(b₂)=0.4;
причем символ b₁
определяется в месте приема сигналом
s₁(t)=0
(0<t<T),
а символ b₂ —
сигналом s₂(t)=a=10^-2
В (0<t<T).
В канале действует белый шум с дисперсией
²=10^-4 В.
Зарегистрированное входное колебание
в момент принятия решения t=T
— z(T)=0.008
В. Какой символ (b₁
или b₂) зарегистрирует
приемник, оптимальный по критерию
максимума апостериорной вероятности?
Найти пороговое значение U₀
для этого приемника.

Решение: Алгоритм работы приемника,
оптимального по критерию максимума
апостериорной вероятности:

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #