13 520
правок
Изменения
→Теория кодирования
== Теория кодирования ==
Первые 3 вопроса берутся из {{Скачать|Яблонский - Введение в дискретную математику.djvu}}, можно также (но хуже) из лекций Алексеева: {{Скачать|Алексеев - лекции по дискретной математике 2002.pdf}}.
==== Алфавитное кодирование. Критерии однозначности декодирования. Неравенство Крафта—Макмиллана ====
* '''Опр.''' кодирование: алфавитное, взаимно однозначное, равномерное, префиксное, постфиксное; неприводимое слово.
* '''Т.''' (Маркова) если кодирование неоднозначно, существуют два слова не длиннее целой части 0.5(W+1)(L-r+2), имеющие одинаковый код.
* '''Т.''' (Макмиллана) если кодирование однозначно, то <m>\sum{i=1}{r}\frac{1}{q^{l_i}} \le 1</m>.
==== Оптимальное кодирование. Построение кодов с минимальной избыточностью ====
* '''Опр.''' цена кода, оптимальный код, код Хаффмана.
* '''У.''' если существует оптимальный код, существует оптимальный префиксный код с теми же длинами слов.
* Алгоритм построения кода с мин.избыточностью — редукция списка вероятностей.
* ''Отсебятина: а ещё есть [[rupedia:Арифметическое кодирование|арифметик]]…''
==== Самокорректирующиеся коды. Граница упаковки. Коды Хемминга, исправляющие единичную ошибку ====
* '''Опр.''' самокорректирующиеся коды.
* [[rupedia:Код Хемминга]] — исправляющий одну ошибку равномерный код, в котором i-ый контрольный разряд — сумма информационных разрядов с номерами, включающими 1 в i-ой позиции двоичной записи.
* '''Т.''' расстояние между любыми двумя кодовыми словами кода Хэмминга ≥ 3.
* '''Т.''' расстояние между кодовыми словами кода, исправляющего k ошибок ≥ 2k+1.
==== Конечные поля и их основные свойства ====
* Можно почитать [[rupedia:Кольцо (математика)]].
* Поле — коммутативное кольцо с единицей, в котором для всякого ненулевого элемента есть обратный.
*
==== Коды Боуза—Чоудхури—Хоквингема ====
* Можно почитать [[rupedia:Код Боуза — Чоудхури — Хоквингема]], как пример - пример — [[rupedia:Код Рида — Соломона]].
== Управляющие системы ==
