Теорема исходного кода
Код, созданный дискретным источником без памяти, должен быть эффективно представлен, что является важной проблемой в коммуникациях. Для этого существуют кодовые слова, которые представляют эти исходные коды.
Например, в телеграфии мы используем азбуку Морзе, в которой алфавиты обозначаются как Marks а также Spaces. Если письмоE считается, который используется чаще всего, он обозначается “.” В то время как письмо Q который редко используется, обозначается “--.-”
Давайте посмотрим на блок-схему.
куда Sk является выходом дискретного источника без памяти и bk является выходным сигналом исходного кодировщика, который представлен 0s а также 1s.
Закодированная последовательность такова, что ее удобно декодировать в приемнике.
Предположим, что в источнике есть алфавит с k разные символы и что kth символ Sk происходит с вероятностью Pk, где k = 0, 1…k-1.
Пусть двоичное кодовое слово, присвоенное символу Sk, кодировщиком длиной lk, измеряется в битах.
Следовательно, мы определяем среднюю длину кодового слова L исходного кодера как
$$ \ overline {L} = \ displaystyle \ sum \ limits_ {k = 0} ^ {k-1} p_kl_k $$
L представляет среднее количество бит на исходный символ
Если $ L_ {min} = \: минимум \: возможно \: значение \: из \: \ overline {L} $
затем coding efficiency можно определить как
$$ \ eta = \ frac {L {min}} {\ overline {L}} $$
С $ \ overline {L} \ geq L_ {min} $ у нас будет $ \ eta \ leq 1 $
Однако исходный кодировщик считается эффективным, если $ \ eta = 1 $.
Для этого необходимо определить значение $ L_ {min} $.
Обратимся к определению: «Учитывая дискретный источник энтропии без памяти $ H (\ delta) $, средняя длина кодового словаL для любой исходной кодировки ограничивается $ \ overline {L} \ geq H (\ delta) $. "
Проще говоря, кодовое слово (пример: азбукой Морзе для слова QUEUE является -.- ..-. ..-.) Всегда больше или равно исходному коду (например, QUEUE). Это означает, что символы в кодовом слове больше или равны алфавитам в исходном коде.
Следовательно, с $ L_ {min} = H (\ delta) $ эффективность исходного кодировщика с точки зрения энтропии $ H (\ delta) $ может быть записана как
$$ \ eta = \ frac {H (\ delta)} {\ overline {L}} $$
Эта теорема исходного кода называется noiseless coding theoremпоскольку он устанавливает безошибочное кодирование. Его также называютShannon’s first theorem.