курсак / поясн
.docx1.Эффективное статистическое кодирование
Эффективное кодирование определяется статистическими взаимосвязями и призвана уменьшить количество разрядов на описание архи- вацию и представление.
Все методы и алгоритмы определяют апостприорную информацию то есть сколько символов рассматривается в данном фрагменте и сколько оди- наковых символов есть в фрагменте.
Когда-нибудь наступит тот день, когда сам Бог скажет Водолеям: "Фиг с вами, ненормальные, пусть будет по-вашему!". //114 симфолов
p(a1)=к=3/114=0,02631
p(a2)=о=8/114=0,07017
p(a3)=г=4/114=0,03508
p(a4)=д=6/114=0,05263
p(a5)=а=8/114=0,07017
p(a6)=н=6/114=0,05263
p(a7)=и=4/114=0,03508
p(a8)=б=3/114=0,02631
p(a9)=у=5/114=0,04385
p(a10)=ь=4/114=0,03508
p(a11)=_=15/114=0,13171
p(a12)=-=2/114=0,01754
p(a13)=с=5/114=0,04385
p(a14)=т=7/114=0,0140
p(a15)=п=3/114=0,02631
p(a16)=е=7/114=0,0140
p(a17)=м=5/114=0,04385
p(a18)=ж=1/114=0,00877
p(a19)=в=3/114=0,02631
p(a20)=я=1/114=0,00877
p(a21)=:= 1/114=0,00877
p(a22)= «=2/114=0,01754
p(a23)=!= 1/114=0,00877
p(a24)=.= 1/114=0,00877
p(a25)=,= 3/114=0,02631
p(a26)=ф=1/114=0,00877
p(a27)=р=1/114=0,00877
p(a28)=ы=1/114=0,00877
p(a29)=л=2/114=0,01754
p(a30)=ш=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 |
S2=U1+U3+U4=1+0+0=1
S3=U2+U3+U4=1+0+0=1
Ответ 0111100
-все
комбинации кода
Чому дорівнює загальна кількість комбінацій 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 таких комбинаций, которые не содержат большого количества нулей, а остальные считать запрещенными кодами. Кроме устранения постоянной составляющей и придания коду свойства самосинхронизации, избыточные коды позволяют приемнику распознавать искаженные биты. Если приемник принимает запрещенный код, значит, на линии произошло искажение сигнала.