Хаффман әдісі бойынша дискретті хабарламаны оптималды кодттау

Әдіс келесілермен қорытындыланылады.

Қор көзі алфовитінің элементтері олардың ықтималдылықтарының кему реті бойынша орналасады.

Одан кейін екі төменгі элемент біріктіріліп жаңа іріктендірілген элемент шығады, ол алфовитте қосындылық ықтималдылығына сәйкес орналасады.

Соңғы екі ықтималдылық қосындысы бірге тең болмайынша 2 п. Орындау жалғаса береді.

Әр біріктіру кезінде элементке 0 санын береміз, біріктірілген қос элементтің жоғарғы жағында орналасқан және 1 санын егер ол төменгі жақта орналасса.

КАНАЛ БОЙЫНША ШУМЕН БЕРІЛГЕНДЕРДІ БЕРУ ПРИНЦИПТЕРІ

аҚПАРАТТЫ БЕРУ ЖЫЛДАМДЫҒЫ ЖӘНЕ ШУМЕН ДИСКРЕТТІ КАНАЛДЫҢ ӨТКІЗГІШТІК ҚАБІЛЕТТІЛ
Х хабарлама көзіне x₁, x₂, ...., x_n элементтерінен хабарлама көзі хабарлама жіберсін, ал хабарламаны алушы кейбір элементтерінен y₁, y₂, ...., y_n тұратын Y кейбір хабарламасын қабылдасын. Хабарлама канал бойынша шумен беріледі.

x₁ y₁

x₂ y₂

... ...

Егер y_i қабылдасақ, онда әр-түрлі ықтималдылықпен x_i берілді деп айтамыз. Если принят, то можно лишь говорить, что с различными вероятностями были переданы, мұндағы i=1,...,n. Мұндай беріліс шартты p(x_i/y_j) ықтималдылық көмегімен математикалық түсіндіріледі.

Егер каналда шу болмаса, онда p(x₁/y₁) =1, p(x₁/y₂) =0 және қалған барлығы p(x₁/y_n) = 0.

Беріліске дейін хабарлама энтропиямен сипатталады H(x_i)=log 1/p(x_i)= -log p(x_i). (*)

H(x_i) шамасы шартсыз немесе априорлы энтропия деп аталады. Шу болған жағдайда хабарлама нәтижесінде энтропия нольге дейін азаяды, қалдықты энтропия шамасына дейін

H(x_i/y_j)=log 1/p(x_i/y_j) = -log p(x_i/y_j). (**)

H(x_i/y_j) шамасы шартсыз немесе априорлы энтропия деп аталады. Анықтаймыз

Ш(ч_ш.н_о)= Р(ч_ш) - Р(ч_ш.н_о) = дщп (з(ч_ш.н_о)).з(ч_ш)ю (1)

ЭНТРОПИЯ H(Х) H(Х/Y)

АҚПАРАТ 0 H(X)-H(X/Y)
Жағдайды қарастырамыз:

1. Шу болмаған жағдайды, яғни әрбір берілген символға бір ғана қабылданған сигнал сәйкес келеді.

p(x_i/y_j)=1 немесе 0, H(x_i/y_j) = 0 ізінше H(X/Y) =0 және I(X/Y)=H(X), яғни жоғалған ақпарат жоқ.

2. Шу деңгейі жоғары болғаны сондай, қабылданған хабарлама беретін хабарламамен байланыспайды.

p(x_i/y_j)= p(x_i), H(x_i/y_j)=H(x_i) ізінше H(X/Y) = H(X) и I(X/Y)=0, яғни толығымен ақпаратты жоғалту жүреді.

Сондықтан 0  I(X/Y)  H(X) =I(X).

Шумен дискретті канал бойынша ақпаратты беру жылдамдығы

R = V_к I(X/Y) бит/с.,

Мұнда

V_к – канал бойынша символдарды беру жылдамдығы;

С = max R – шу болған кездегі каналдың өткізгіштік қасиеті.

Көріп отырғандай, шу болған жағдайда каналдың өткізгіштік қасиеті кемиді.
Шумен дискретті канал бойынша Шеннон теоремасының өткізгіштік қасиеті
Тура теоремасы:

Если производительность источника сообщения P хабарлама көзінің өнімділігі С каналының өткізгіштік қабілеттілігінен аспайтын болса Р  С онда шудың болғанына қарамастан кодттаудың мынандай әдісі болады, беру кезінде ақпарат жоғалмайды, Р  С кезінде, ақпаратты беру жылдамдығы С (R  С) ұмтылады.

Кері теорема.

Егер Р > C, онда ақпаратты жоғалтусыз беру кодттау әдісі болмайды.

Бұл теоремада кодттаудың дәл бір әдісі көрсетілмеген, ақпарат нольге тең болатын бірақ оның бары дәлелденген.

Мысал.

C_бп = 1000 бит/c C_п = 600 бит/c

Р_бп = 1000 бит/c Р_п = 600 бит/c

V_и^opt = 1000 дв.симв./c V_и^opt = 600 дв.симв./c

Шеннона теоремасына сәйкес шумен канал бойынша ақпаратты қатесіз берудің жалғыз әдісі артықтықты енгізу.

шуға қарсы артықтықты енгізу әдісі

9.1 Шуға қарсы тұрақты (помехоустойчивое) кодттау.

9.2 Қателіктен қорғаудың топтық әдісі.

9.3 Кері байланыспен берілгендерді беру жүйесін ұйымдастыру.
Шуға қарсы тұрақты (помехоустойчивое) кодттау принциптері

Шуға қарсы тұрақты (помехоустойчивое) кодттаудың үш типі болады:

• 
  қатені табумен;
  

• 
  қатені түзетумен;
  
• 
  қатені тауып түзетумен.
  

Шуға қарсы тұрақты (помехоустойчивое) кодттаудың негізгі сипаттамаларын қарастырайық.

Кодттық ара-қашықтықты таңдау үшін теңсіздік пайдаланылады

мұндағы r – берілген код табатын қателер саны;

Шуға қарсы тұрақты (помехоустойчивое) кодттар синтезінің тапсырмасы келесі бейнеде қалыптасуы мүмкін: N_и берілетін хабарлама жиыны берілсін, шуға қарсы тұрақты (помехоустойчивое) кодттың талаптары көрсетілген. Көрсетілген талаптарды орындауда неғұрлым тиімдіні қамтамасыз ететін кодтты синтездеу қажет.

Ол үшін мыналарды анық тау қажет:

• 
  n – кодттық сөздің ұзындығын (разрядность кода);
  
• 
  кодттық қашықтықты d;
  
• 
  n_к бақылаушы символдар қажетті санының минималдылығы және олардың шамалары;
  
• 
  n_и ақпараттық символдар санының хабарлама жиынын беру үшін қажет;
  
• 
  қабылданған хабарлама саны және тексеру реті.
  

Ең бірінші ақпараттық символдар саны анықталады n_и, сосын - n_к.

Бақылаушы символдар санын анықтау үшін n_к келесідей талданады. рассуждают следующим образом. n_к бақылаушы символдардан n_к екілік комбинациядағы дәреже, сұрақтарға «йә» немесе «жоқ» деген жауап беру қажет:

0. 
   Берілген кодттық сөз дұрыс қабылданды ма?
   
1. 
   Егер онда қате болса, онда қандай n позицияда, бақылауды қосқанда? Осы бейнеде, екілік комбинация n + 1 сұрағына кем емес жауап беру керек, яғни
   
2. 
   (2)
   

немесе