Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Задача 1. Код Морзе - типичный пример неравномерного двоичного кода . В нем символы и применяются лишь в двух сочетаниях – как одиночные ( и ) или как тройные ( и ). Сигнал, соответствующий , называется точкой, а – тире. Символ используется как знак, отделяющий точку от тире, точку от точки и тире от тире. Совокупность применяется как знак разделения кодовых слов.
Задача 2. Пусть алфавит источника состоит из символов , . Вероятности появления символов на выходе источника, соответственно, равны , , , , и . Процедура Шеннона-Фано построения неравномерного кода без укрупнения алфавита источника задается табл. 1.1 .
Таблица 1.1. Кодирование источника по методу Шеннона-Фано
|
Выбор символов неравномерного кода |
||||||
|
1 |
2 |
3 |
4 |
|||
|
0,4 0,3 0,1 0,08 0,07 0,05 |
0 1 1 1 1 1 |
0 1 1 1 1 |
0 0 1 1 |
0 1 0 1 |
1 2 4 4 4 4 |
На ом этапе множество символов делим на части: и ; на ом - и ; на ем - и ; на ом - и , и . Более вероятным символам источника присвоим кодовые слова меньшей длины . Построили префиксный код. Средняя длина кодового слова (среднее число символов кода на один символ источника) .
Задача 3. Каждое кодовое слово наиболее простого из линейных систематических двоичных кодов содержит проверочный символ, равный сумме по всех информационных символов. Это - код с проверкой на четность. Для него кодовое расстояние , что позволяет гарантированно обнаружить лишь однократные ошибки. Слова такого кода имеют только четные веса. Вероятность пропуска ошибки в ом приближении равна вероятности искажения х символов: .
Есть видоизмененный способ контроля на четность. Последовательность информационных символов , где , разбивается на строк по символов в каждой так, что . Контрольные разряды , где , выделены каждой строке и каждому столбцу по следующей схеме:
Контроль на четность делается по строкам и по столбцам. Если, например, нарушение четности обнаружено для -ой строки и -ого столбца, то символ матрицы - ошибочный. Исправление обнаруженной ошибки достигается заменой этого символа ( - на или - на ).
Задача 4. Пусть дискретный источник равновероятно выдает двоичную цифру или каждые секунд. Количество информации, доставляемое цифрой, (бит), Пусть последовательные цифры на выходе источника статистически независимы, то есть источник не имеет памяти. Всего есть возможных битовых блоков источника, каждый – с вероятностью и длительностью . Собственная информация блока за время равна (бит).
Определим условную собственную информацию
(2.3)
где - собственная информация события при известном .
Комбинируя (2.1), (2.2) и (2.3), получим
(2.4)
Средняя взаимная информация случайных величин и в расчете на символ
(2.5)
где и - объемы алфавитов и , соответственно. Можно показать, что , и для статистически независимых и .
Средняя условная собственная информация - условная энтропия,
(2.6)
где - неопределенность в значениях (дополнительная информация, содержащаяся в ) после наблюдения .
Энтропия источника равна его средней собственной информации на символ,
(2.7)
Из (2.1), (2.5), (2.6) и (2.7) следует
(2.8)
Из (2.8) и следует и , где равенство верно, если статистически не зависит от . Величина равна уменьшению среднего значения неопределенности значений () за счет измерения (). Пусть - длительность символа источника. Производительность источника - среднее количество информации, выдаваемое им в единицу времени,
(2.9)
Задача 5. Возьмем источник, выдающий последовательность независимых символов: - с вероятностью , и - с вероятностью . Энтропия двоичного источника . Максимальное значение бит (при равновероятных символах), а минимальное - (если возможна передача лишь одного символа).
Для источника с объемом алфавита выразим
.
Так как (), то , или
(2.10)
Наибольшее значение: (информационная емкость алфавита источника), достигается, если символы равновероятны: , . Для передачи количества информации от источника с энтропией требуется символов, а от источника с энтропией - минимальное их число
(2.11)
где - допустимая степень сжатия сообщений, . Величина называется избыточностью источника.
Пусть есть блок из случайных величин с совместной вероятностью . Пусть , , имеет алфавит , , с объемом . Энтропия этого блока, согласно (2.7),
(2.12)
Так как , из (2.12) следует
(2.13)
Так как , где и , из (2.13) имеем:
(2.14)
где равенство верно, если не зависят друг от друга.
Задача 6 . Из (2.17) выразим дифференциальную энтропию гауссовской величины с распределением , средним и дисперсией :
(2.18)
При заданной дисперсии среди случайных непрерывных величин с разными законами распределения наибольшую дифференциальную энтропию имеет гауссовская величина .
Условная дифференциальная энтропия случайной непрерывной величины при заданной :
(2.19)
Учитывая (2.16), (2.17) и (2.19), , найдем
(2.20)
Задача 7. Пусть случайная величина , где и - независимые гауссовские величины с дисперсией и , соответственно. Рассмотрим и как амплитуды импульсов на входе и выходе канала, соответственно, а - как аддитивный шум, добавляющийся к импульсам при передаче по каналу. Согласно центральной предельной теореме теории вероятностей (ЦПТ) , величина - тоже гауссовская с дисперсией . С учетом (2.18) ее дифференциальная энтропия равна . Из (2.19) следует . Но и , так что условная дифференциальная энтропия гауссовской величины зависит лишь от дисперсии шума : . Выражения для и подставим в (2.20). Найдем среднюю взаимную информацию для изучаемого канала: . При введенных ограничениях - максимально возможное количество информации об отсчете входного в канал сообщения в одном отсчете выходного сообщения.
Задача 8. Пусть и - случайные двоичные величины на входе и выходе канала. Пусть входные символы равновероятны. Условные вероятности выходных символов при известном входе заданы как , , и . Найдем, сколько информации об и содержит событие :
Взаимная информация о символе при наблюдении равна
Взаимная информация о символе при наблюдении равна
Для канала без шумов , так что бит. Значит, если выход точно определяет вход, нет потери информации. При обрыве канала, так что - канал непригоден.
Пусть - сообщение источника в канал, а - сообщение, принимаемое приемником. Тогда в (2.8) - среднее количество информации, получаемое приемником с приходом символа, а ненадежность - среднее количество информации, теряемое в канале связи. Шумовая энтропия зависит лишь от помех в канале. Пусть - среднее время передачи символа по каналу. Среднее количество информации, передаваемое по каналу в единицу времени, - скорость передачи информации по каналу
(3.4)
Задача 9. Согласно (2.6) и (3.1), в -ичном симметричном канале без памяти условная энтропия не зависит от передаваемых символов: . Максимальное значение энтропии при равновероятных символах (см. (2.10)). Выражения для и подставим в (2.8). С учетом (3.10) пропускная способность изучаемого канала
(3.11)
Из (3.11) видно, что минимальное значение при . Тогда, согласно (3.1), , так что каждый входной символ равновероятно переходит в любой выходной. Наблюдая выходные символы, нельзя предпочесть ни один из входных. Это означает обрыв канала - передача информации по каналу бесполезна. Тот же результат следует при случайном угадывании входных символов в точке приема. Из (3.11) для двоичного канала максимальное значение бит и при , и при . Случай описывает состояние канала с обратной работой. Тогда при передаче по каналу все переходят в , а - в . Если это заранее известно, при сообщение декодируют по правилу: , .
Из (2.8), (2.10) и (3.10) найдем пропускную способность ичного канала с памятью и аддитивным шумом: . Величина - степень неопределенности в значениях (дополнительная информация в ) при известном . За счет памяти канала эта степень становится меньше, а пропускная способность – больше .
Задача 10. Возьмем ДИБП с символами , , имеющими заданные вероятности выбора. Надо построить двоичный код ().
Построим кодовое дерево (см. рис. 4.1). Символы источника расположим в порядке убывания их вероятностей. Пусть , , , , , и . Кодирование начнем с х наименее вероятных символов и . Их объединим (см. рис. 4.1). Верхнему ветвлению присвоим кодовый символ , а нижнему - . Сложим вероятности этих ветвей. Общему узлу присвоим суммарную вероятность . Теперь есть исходные символы: , и новый символ , полученный объединением и . На следующем этапе снова объединим наименее вероятных символа и с суммарной вероятностью из набора: . Переходу от символа присвоим кодовый символ , а переходу от символа - . Процедуру продолжим, пока не исчерпаем все возможные символы источника. Результат – кодовое дерево с ветвями, содержащими искомые кодовые слова.
Кодовые слова (см. табл. 4.1) получаются, если двигаться от самого правого узла дерева, переходя к самому левому узлу. Среднее число кодовых символов на символ источника бит/символ, а энтропия источника - бит/символ.
0
1
0,01
0
1
0,05
1
0
0,15
1
0
0,65
0,35
0
1
0,35
0,30
0,20
0,10
0,04
0,005
0,005
Рис. 4.1. Построение кодового дерева
Таблица 4.1. Кодовые слова кода Хаффмена и их характеристики
|
Символ |
Вероятность |
Собственная информация |
Код |
|
0,35 |
1,5146 |
00 |
|
|
0,30 |
1,7370 |
01 |
|
|
0,20 |
2,3219 |
10 |
|
|
0,10 |
3,3219 |
110 |
|
|
0,04 |
4,6439 |
1110 |
|
|
0,005 |
7,6439 |
11110 |
|
|
0,005 |
7,6439 |
11111 |
На предпоследнем шаге процедуры кодирования был равный по вероятности выбор между и . Здесь были соединены и . Вместо этого в альтернативном коде можно было бы соединить и , получив символ . На последнем шаге построения кодового дерева соединялись бы символы и . Для альтернативного кода среднее число битов на символ тоже равно , как и для кода на рис. 4.1. То есть, полученные коды одинаково эффективны. Назначение верхнему переходу и - нижнему (менее вероятному) переходу, выбрано произвольно. Поменяв местами и , получим еще два эффективных префиксных кода.
Задача 11. Возьмем гауссовский источник без памяти с ФПВ , математическим ожиданием и дисперсией . Из (5.1) для среднеквадратичной ошибки на символ () в качестве меры искажения
где при никакой информации передавать не надо.
Задача 12. Оптимальный уровневый () неравномерный квантователь для гауссовской амплитуды сигнала с нулевым средним и единичной дисперсией, согласно (5.3), описан в табл. 5.2.
Таблица 5.2. Уровни оптимального уровневого неравномерного квантователя
|
Уровень |
|
1 -0,9816 -1,510 2 0,0 -0,4528 3 0,9816 0,4528 4 1,510 |
Вероятности символов на выходе квантователя: - для двух внешних уровней и - для двух внутренних уровней. Тогда энтропия дискретного источника бит/символ.
Квантователь превращает непрерывную амплитуду источника в дискретную. Дискретные амплитуды трактуем как символы с вероятностями . Выход квантователя можно подвергнуть энтропийному кодированию для повышения эффективности сжатия данных. При независимых отсчетах амплитуды сигнала на выходе квантователя получим дискретный источник без памяти с энтропией .
Задача 13. У систематического кода с порождающей матрицей
кодовое слово - , где - информационных бита, - проверочных бита, и Кодер для этого кода показан на рис. 6.1.
Входные
данные
Выходные
данные
Рис. 6.1 Схема кодера блокового линейного кода
Для любого линейного кода существует дуальный (двойственный) код . Любое кодовое слово кода ортогонально любому кодовому слову дуального кода. Порождающая матрица размерности дуального кода имеет линейно независимых векторов-строк, причем
, (6.2)
где - вектор-столбец из нулей. В частности, , где - матрица из нулей размерности . Для систематического кода с порождающей матрицей дуальный код имеет порождающую матрицу
, (6.3)
где для двоичного кода знак минус можно опустить, так как вычитание по идентично сложению по . Подставив (6.3) в (6.2), найдем уравнения проверки
(6.4)
где , - элементы канонической матрицы , образующие матрицу , - ый элемент кодового слова .
В (6.4) проверочные символы кодовых слов образованы разными линейными комбинациями информационных символов. Матрицу называют также проверочной матрицей кода . Она позволяет построить код с заданным кодовым расстоянием, согласно следующей теореме.
Задача 14. Для циклического кода с порождающим полиномом проверочный полином (см. (6.12)). Из соотношения следуют уравнения проверки. Умножая и приравнивая коэффициенты при , и в произведении, выразим проверочные символы: , , . На рис. 6.3 показана схема кодера циклического кода .
Т1
Т2
Т3
Т4
Выход
m2
m2
2
Рис. 6.3. Схема кодера циклического кода с проверочным полиномом ; - ячейки сдвигающего регистра, - сумматор по
Сначала ключ - в положении . В течение х тактов информационная последовательность поступает в регистр. Затем ключ переходит в положение , обратная связь замыкается. С го такта образуются проверочные символы, согласно найденным для них выражениям. После го такта проверочные символы образованы, ключ переходит в положение . Кодер готов к приему нового сообщения. Символы кодового слова поступают из кодера в канал с го такта.
Корректирующая способность кода зависит от его порождающего полинома степени, равной числу проверочных символов, причем делит . Пусть () - полином переданного (принятого) кодового слова (). Тогда , где - полином вектора ошибок , . Поиск ошибок кодом состоит в делении на . Считают, что ошибок нет, если только остаток деления .
Для кода, обнаруживающего все одиночные ошибки, полином ошибок , . Самый простой полином , не делящий полином , - . Согласно (6.11), делится на . Остаток от деления на зависит лишь от вектора ошибки. Ошибки можно исправить, используя таблицу соответствия между и в памяти декодера. Цикличность упрощает декодирование. Пусть циклический код с кодовым расстоянием исправляет все ошибки кратности ( - целая часть от ). Один из алгоритмов исправления ошибок основан на свойствах синдрома такого кода:
а) если искажены лишь проверочные символы, вес вектора синдрома , а сам синдром совпадает с вектором ошибок;
б) если искажен хоть информационный символ, вес синдрома ;
в) если - остаток от деления на , остаток от деления на - полином ; то есть, синдром некоторого циклического сдвига полинома является соответствующим циклическим сдвигом синдрома исходного полинома.
Задача 15. На рис. 6.7 показан сверточный кодер ( и ). Информационная последовательность из дает кодовую последовательность из . Табл. 6.2 - пример получения кодовой последовательности.
Вход
Рис. 6.7. Двоичный сверточный кодер для кода со скоростью
Таблица 6.2. Получение кодовой последовательности в кодере рис. 6.7
|
Вход |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
Выход |
11 |
10 |
11 |
00 |
11 |
01 |
01 |
11 |
00 |
Задача 16. На рис. 6.12 показано разбиение множества сигналов с 8-ричной ФМ. Созвездия находятся в нижнем ряду рисунка.
1
5
2
4
0
6
3
1
5
7
3
7
2
4
0
6
3
1
5
7
4
0
2
6
Рис. 6.12. Разбиение 8-ричных ФМ сигналов на созвездия
Кодер Унгербоека (см. рис. 6.13), отображая сигналы созвездиями, обеспечивает наибольшее кодовое расстояние между последовательностями кодированных сигналов и высокую спектральную эффективность их представления. Двоичная последовательность символов разбита на блоки по бит. Первые бит блоков подают на вход сверточного кодера, остальные - без кодирования на модулятор. Биты без кодирования задают сигнал в созвездии, а кодированные - выбор созвездия. Для схемы разбиения рис. 6.12 параметры кодера рис. 6.13: , , . Евклидовы расстояния между сигналами в каждом из созвездий много больше минимального расстояния между сигналами разных созвездий.
Биты без кодирования
Кодированные биты
Сверточный кодер со скоростью
Рис. 6.13. Кодер Унгербоека
Задача 17. Логический код 4B/5B для технологий FDDI и Fast Ethernet заменяет входные в кодер битовые символы выходными битовыми. Последние содержат избыточные биты. Количество битовых комбинаций на выходе больше, чем на входе. В коде 4B/5B есть () выходных (входных) символов. Среди выходных можно взять символов с небольшим числом и сделать их разрешенными. Остальные символов – запрещенные. Соответствие символов входного битового кода символам выходного битового кода показано в табл. П.1.
|
Исходный код Результирующий код Исходный код Результирующий код |
|
0000 11110 1000 10010 0001 01001 1001 10011 0010 10100 1010 10110 0011 10101 1011 10111 0100 01010 1100 11010 0101 01011 1101 11011 0110 01110 1110 11100 0111 01111 1111 11101 |
Построенный код, например, - , передается по линии с помощью физического кодирования (одним из методов ПК, чувствительным лишь к длинным последовательностям из ). При битовых символах кода на линии нет более трех подряд. Буква в названии кода означает, что элементарный сигнал - двоичный. Есть еще коды с ичными элементарными сигналами. В коде 8B/6T каждые бит исходной информации закодированы ю сигналами с мя возможными состояниями у каждого. Избыточность кода выше, чем кода , так как для исходных символов есть результирующих. Применение таблицы перекодировки не усложняет сетевые адаптеры и интерфейсные блоки коммутаторов и маршрутизаторов. При заданной пропускной способности линии передатчик, применяющий избыточный код, работает на повышенной тактовой частоте. При передаче символов кода со скоростью Мб/с тактовая частота передатчика - МГц . Спектр сигнала шире (уже), чем в простом (манчестерском) коде. Значит, логическое кодирование и работа передатчика на повышенной тактовой частоте оправданы.
Перемешивание данных до передачи – другой метод логического кодирования. Скремблер побитно вычисляет логический код на основе битов исходного кода и битов логического кода с предыдущих тактов.
Задача 18. Пусть скремблер делает операцию . Здесь () - двоичная цифра кода на входе (выходе) для го такта работы скремблера, и - двоичные цифры выходного кода для тактов с номерами и , соответственно, - операция исключающего ИЛИ (сложения по ). Для входной комбинации выходной код
Первые цифры выходного и входного кодов соответственно совпадают, так как нет нужных предыдущих цифр. Комбинация появится на выходе скремблера. В ней нет и нулей подряд, как на входе. Получив выходную комбинацию, приемник передает ее дескремблеру, который восстанавливает входную комбинацию на основании обратного соотношения: .