курсак / поясн

1.Эффективное статистическое кодирование

Эффективное кодирование определяется статистическими взаимосвязями и призвана уменьшить количество разрядов на описание архи- вацию и представление.

Все методы и алгоритмы определяют апостприорную информацию то есть сколько символов рассматривается в данном фрагменте и сколько оди- наковых символов есть в фрагменте.

Когда-нибудь наступит тот день, когда сам Бог скажет Водолеям: "Фиг с вами, ненормальные, пусть будет по-вашему!". //114 симфолов

p(a₁)=к=3/114=0,02631

p(a₂)=о=8/114=0,07017

p(a₃)=г=4/114=0,03508

p(a₄)=д=6/114=0,05263

p(a₅)=а=8/114=0,07017

p(a₆)=н=6/114=0,05263

p(a₇)=и=4/114=0,03508

p(a₈)=б=3/114=0,02631

p(a₉)=у=5/114=0,04385

p(a₁₀)=ь=4/114=0,03508

p(a₁₁)=_=15/114=0,13171

p(a₁₂)=-=2/114=0,01754

p(a₁₃)=с=5/114=0,04385

p(a₁₄)=т=7/114=0,0140

p(a₁₅)=п=3/114=0,02631

p(a₁₆)=е=7/114=0,0140

p(a₁₇)=м=5/114=0,04385

p(a₁₈)=ж=1/114=0,00877

p(a₁₉)=в=3/114=0,02631

p(a₂₀)=я=1/114=0,00877

p(a₂₁)=:= 1/114=0,00877

p(a₂₂)= «=2/114=0,01754

p(a₂₃)=!= 1/114=0,00877

p(a₂₄)=.= 1/114=0,00877

p(a₂₅)=,= 3/114=0,02631

p(a₂₆)=ф=1/114=0,00877

p(a₂₇)=р=1/114=0,00877

p(a₂₈)=ы=1/114=0,00877

p(a₂₉)=л=2/114=0,01754

p(a₃₀)=ш=1/114=0,00877

Согласно эффективному кодированию существует 2 способа:

1й- метод Шеннона-Фано

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

Затем полученную последовательность делем на приблизительно боль-шую и меньшую части большей приревниваем-1, меньшей-0. Затем работаем с каждым подмножеством отдельно и так же делим на большую и меньшую части это происходит до тех пор пока в подмножестве не останеться одно значение (см.Додаток А)

=0.14*4+0.12*4+0.08*3+0.08*4+0.06*4+0.06*3+0.04*5+0.04*5+0.04*4+

+0.04*5+0.04*5+0.04*4+0.04*5+0.04*5+0.04*4+0.02*6+0.02*6+0.02*5+0.02*5+0.02*5=4.24

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

Недостаток способа является неоднозначность выбора подгруппы при делении так как если в группе в верхней части был приравнен 1, а нижней 0, то может произойти что при очередном делении вероятность может оказаться меньшим значением. Полученное значение эффективного кодирования будет сравниваться с энтропией источника Бернули так как вероятности появления символов не одинаковы как для источника Харкли.

0.3071+0.3671+0.2915*2+0.2435*2+0.1857*9+0.1129*5=3.98

2й-метод Хаффмена

Для данного метода он устраняет неоднозначность предыдущего спо-соба но согласно разным вероятностям появления могут оказаться эффек-тивными или нет.

При построении и вычислении кодовой последовательности так же как и в методе Шеннона-Фано вероятность появления описываются столбцом в порядке убывания

Две наименьших вероятности складываем больше из этих 2х прирав-ниваем к1, меньшей к 0, затем полученную сумму устанавливаем в ранее по-лученных вероятностей в порядке убывания сложение производиться до тех пор пока сумма не будет равна 1. Додаток Б

Для получения кодов следует построить кодовое дерево. Сами коды мы находим из кодового дерева сверху в низ. Додаток В

=0.14*3+0.12*3+0.08*4+0.08*4+0.06*4+0.06*4+0.04*5+0.04*5+0.04*4+

+0.04*4+0.04*4+0.04*4+0.04*5+0.04*5+0.04*5+0.02*5+0.02*6+0.02*6+0.02*6+0.02*6=4.12

Додаток В

a3 101

a13 011

a2 1101

a15 1100

a7 1000

a11 0101

a1 10011

a4 10010

a8 0001

a9 0000

a12 0011

a14 0010

a16 11101

a17 11100

a20 11111

a5 01000

a6 010011

a10 010010

a18 111101

a19 111100 /92 символа

Завдання № 1

Визначте число коректуючих розрядів систематичного коду, який виправляє всі подвійні помилки, якщо загальна довжина коду дорівнює 28.

Завдання № 2

Задана безнадмірна кодова комбінація. Потрібно закодувати її у коді Хєммінга (7, 4), визначити символи всієї кодової комбінації(1100)

N поз. код. комб.	К1	К2	U1	К3	U2	U3	U4
Двоичный код позиции	001	010	011	100	101	110	111
Значение инф. разряда	S1	S2	1	S3	1	0	0
Символы кодовой комбинации	0	1	1	1	1	0	0

S1=U1+U2+U4=1+1+0=0

S2=U1+U3+U4=1+0+0=1

S3=U2+U3+U4=1+0+0=1

Ответ 0111100

-все комбинации кода

Завдання № 3

Чому дорівнює загальна кількість комбінацій 8 значного двійкового коду з постійною вагою W = 1 Побудувати всі комбінації такого коду.

Содержание

Вступление	2
1.Эффективное статистическое кодирование	3
1й- метод Шеннона-Фано	4
Метод Бернули	6
2й-метод Хаффмена	7
Задача №1	8
Задача № 2	8
Задача № 3	9
Додаток А	10
Додаток Б	11
Додаток В	12
Додаток Г	13

Вступление

Логическое кодирование используется для улучшения потенциальных кодов типа AMI, NRZI или 2Q1B. Логическое кодирование должно заменять длинные последовательности бит, приводящие к постоянному потенциалу, вкраплениями единиц. Для логического кодирования характерны два метода — избыточные коды и скрэмблирование.

Избыточные коды основаны на разбиении исходной последовательности бит на порции, которые часто называют символами. Затем каждый исходный символ заменяется на новый, который имеет большее количество бит, чем исходный. Например, логический код 4В/5В, используемый в технологиях FDDI и Fast Ethernet, заменяет исходные символы длиной в 4 бита на символы длиной в 5 бит. Так как результирующие символы содержат избыточные биты, то общее количество битовых комбинаций в них больше, чем в исходных. Так, в коде 4В/5В результирующие символы могут содержать 32 битовых комбинации, в то время как исходные символы — только 16. Поэтому в результирующем коде можно отобрать 16 таких комбинаций, которые не содержат большого количества нулей, а остальные считать запрещенными кодами. Кроме устранения постоянной составляющей и придания коду свойства самосинхронизации, избыточные коды позволяют приемнику распознавать искаженные биты. Если приемник принимает запрещенный код, значит, на линии произошло искажение сигнала.