16. Словарные методы: Лемпеля-Зива и Лемпеля-Зива-Велча. Правила построения. Достоинства и недостатки кодов. Применение.

Метод Л-З(LZ):

1. Последовательность символов делится на блоки переменной длины, которые называются фразами.

2. Каждая новая фраза должна отличаться от всех предыдущих и в одном символе от одной из предыдущих фраз.

3. Все фразы записываются в словарь, который сохраняет расположение существующих фраз.

4. Кодовые слова состоят их 2х частей:

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

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

Средний

Метод Л-З-В(LZV):

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

2. Фраза закрепляется за номером словаря.

3. Если фраза состоит из 2х символов, то выходной код соответствует 1му символу фразы (левому), а если фразу составляют большие числа символов, то выходной код соответствует номеру словаря.

Средний

Более эффективен, чем LZ. Применяется в архиваторах для сжатия текстов.

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

Т. Шенона:

Прямая: если источник с энтропией H(B) создает информацию на входе шумящего канала без памяти со скоростью R меньшей, чем пропускная способность C данного канала, то существует такой код, при котором вероятность ошибки на принятом конце сколь угодно мала.

Обратная: если скорость создания информации R больше пропускной способности канала, то никакой код не может обеспечить сколь угодно малой ошибки.

Код выбирают для обеспечения:

- высокого выигрыша по энергии (можем использовать маленькие антенны, маломощные передатчики, дальше расстояние)

- от вероятности ошибок в КС

- от скорости передачи

- простота реализации

- спектр частот

- в зависимости от типа линии связи, и от видов помех:

*проводные КС: они более защищены от помех, чем радиолинии; учитывают:

+ импульсные помехи (атмосферные явления)

+ наводки от внешних источников

+ межсимвольные искажения

+ нелинейность АЧЧХ

*радиолинии (радиорелейные, космические, ЛС с подв. объектами) больше шума, помехи от внешних источников.

*внутриаппаратные тракты: ошибки за счет устройств ввода/вывода, линий информационного обмена, устройств памяти, старения элементов, расфазировки сигналов на входе элементов.

№	Канал	Коды и алгоритмы декодирования	Особенности
1	Пров ЛС с 0 уровнем ош.	Коды, обнаруживающие ош. + сист с ОС	Повышение Pош приводит к уменьшению R
2	Пров. ЛС небольшой протяж.	БЧХ,РС,РМ,Хэмминга	n=15
3	Pош>10^-3	Те же + Голлея	n>15
4	Pош>0 больш. Расст.	Каскадные коды	Ув. Dmin при простом кодек
5	Радио с бел Гауссовским шумом	1.Сверт. код+ алг. Витерби 2. Сверт. код+ многопороговое декодирование	1. если m<g – память кода: Ув. m-> ув. ЭВК-> Ув. сл-ть 2. m>g, ЭККмпд< ЭВКвит – проще
6	Pош>0,1	Турбокоды	при С/Ш 0,5 дБ
7	Внутриаппаратные и ЗУ	->КОО c небольш. ->иттеративный код