 |
Кодери згортальних кодів.
|
|
|
|
Білет №19
1. Загальна характеристика кодерів загортальних кодів
2. Потенційна перешкодостійкість двійкового каналу зв’язку, критерій ідеального спостерігача
Відповіді
Кодери згортальних кодів.
Визначення. Лінійний постійний у часі деревоподібний ( 
, 
)- код, що має кінцеву довжину слова 
, називається згортальним ( 
, 
)- кодом. Згортальний ( , )- код, що задовольняє умові систематичності, називається систематичним згортальним ( , )- кодом.
Помітимо, що ми можемо називати той самий код деревоподібним ( , )- кодом або згортальним ( , )- кодом.
Рис. 2. Приклади згортальних кодерів.
|
і 
. Перший з них служить кодером для систематичного двійкового ( 
) згортального (12, 6)- коду з довжиною кодового обмеження, рівного 
, другий є кодером для несистематичного двійкового згортального (6, 3)- коду з довжиною кодового обмеження 
.
В обох випадках вхідні символи перетворяться двома фільтрами (КІХ- фільтрами – з кінцевою імпульсною характеристикою), один із яких утвориться верхніми відводами, а іншої – нижніми. Символи з виходів цих двох фільтрів поперемінно в часі зчитуються і подаються в буфер по одному символі в одиницю часу з кожного виходу; їхнє зчитування з буфера виробляється вдвічі частіше, ніж надходять вхідні символи.
Відомо кілька способів опису роботи згортальних кодерів. Обговоримо їх більш докладно.
Згортальний кодер, як кінцевий автомат з пам'яттю, може бути описаний діаграмою станів. Можливі 
станів кодеру описуються при 
і 
символами 
(рис. 2, б), тобто кодер може знаходитися в одному з 4-х можливих станів = 00, 01, 10, 11, причому стан 
характеризує останній інформаційний символ. Діаграма станів являє собою спрямованого графа, що містить усі стани і можливі переходи з одного стану в інше, описувані виходами 
кодеру (кодовими символами кадру). Діаграма станів приведена на рис. 3.
|
|
|
У кружках зазначені стани кодеру ( 
), стрільцями – можливі переходи. Біля стрілок показані символи на виході кодеру ( 
), що відповідають кожному переходові.
| Рис. 3. Діаграма функціонування згортального (6, 3)-кода. |
| S1 S2® |
| с1 с2 ® |
= 00. Наступний запис вхідного символу «0» у переводить його також у стан « 00 ». На діаграмі цей перехід позначений петлею «00» біля стану « 00 ». Далі, при надходженні на вхід символу «1» на виході кодеру формуються кадр кодових символів «11» з наступним переходом кодеру в стан « 10 ». Цей перехід зі стану « 00 » у стан « 10 » позначається стрілкою, супроводжуваної кодом «11», і т. д. Побудова діаграми закінчується, коли переглянуті всі можливі переходи з кожного стану в усі інші. Процес формування діаграми рис. 3 розглянемо на прикладі.
Задача 1. Побудувати діаграму функціонування згортального (6, 3)-коду.
Рішення.
Подамо на вхід згортального кодера рис. 2, б інформаційну послідовність 
(тут як і колись молодші розряди ліворуч). Процес формування діаграми функціонування згортального (6, 3)- коду наочно ілюструє табл. 1.
Таблиця 1
| Такт |
| Вхід кодера | Состояния кодера | Виходи кодера | ||||||||
| u0 | u1 | u2 | u3 | u4 | S0 | S1 | S2 | c1 | c2 | |||
|
| ||||||||||||
|
| ||||||||||||
|
|
| |||||||||||
|
|
|
| ||||||||||
|
|
|
|
| |||||||||
|
|
|
|
|
| ||||||||
|
|
|
|
|
| ||||||||
|
|
|
|
|
| ||||||||
Розгорнення станів у часі утворить, так звану, решітчасту діаграму (рис. 4) (звідси назва – решітчасті коди), на якій стани показані вузлами, а переходи – з'єднуючими їхніми лініями, супроводжуваними значеннями символів ( 
) кодового слова.
Рис. 4. Решітчаста діаграма згортального (6, 3)-коду.
Решітчаста діаграма – граф, вузли якого знаходяться в прямокутній координатній сітці, напівнескінченної праворуч; число вузлів у кожнім стовпці кінцево. Конфігурація ребер, що з'єднують вузли кожного стовпця з вузлами стовпця праворуч, однакова для всіх стовпців. Вузли, що не можуть бути досягнуті при русі вправо з верхнього лівого вузла, звичайно не вказуються.
Вузли в кожному стовпці решітки представляють станів, у яких може знаходитися регістр зсуву. Кожен наступний стовпець решітки являє собою набір станів у наступний момент часу.
Надходження на вхід нового інформаційного кадру приводить до зміни стану регістра зсуву, що відповідає ребру, що веде до наступного вузла. У розглянутому прикладі кожне ребро позначене двома двійковими символами, переданими в канал при переході в наступний стан регістра зсуву. Тут ведуча з довільного вузла верхня пряма відповідає нульовому вхідному двійковому символові, а нижня – одиничному. У загальному ж випадку кожне ребро позначається 
вихідними символами, що йому відповідають.
Маркірована решітка описує згортальний код у тім смислі, що всі шляхи від вузла до вузла ліворуч праворуч по решітці позначають кодові слова. Маркірування ребер однакове для кожного сегмента (часового кадру) і лінійна в тім смислі, що лінійна комбінація маркірувань будь-якої безлічі ребер є маркіруванням деякого ребра.
Помітимо, що решітка може бути маркірована і при інших обмеженнях (див. розглянуті вище властивості) або при їхній повній відсутності. Якщо маркірування не має властивість лінійності, то, як ми уже вказували, код називається ковзним блоковим кодом. Якщо маркірування міняється від кадру до кадру, то такий код відомий під загальною назвою решітчастого коду. Нарешті, якщо число станів у наступних друг за другом часових кадрах продовжує необмежено рости, те такий код називається загальним деревоподібним кодом.
|
|
|
|
Рис. 5. Ілюстрація процесу кодування згортального (6, 3)-коду
на решітчастій діаграмі.
|
.
Рішення.
Решітчаста діаграма зображує всі дозволені шляхи, по яких може просуватися кодер при кодуванні. Жирною лінією на рис. 5 показаний шлях по решітці 11®10®00®01®10, що відповідають надходженню на вхід кодера інформаційної послідовності 1 0 1 1 1. Відповідно галузям решітчастої діаграми в міру просування одержуємо кодові посилки 11. 10. 00. 01. 10... і т. д.
Білет №20
1. Декодування загортальних кодів. Алгоритм Вітербі.
2. Характеристика послуг безпеки відповідно до стандарту.
Відповіді
|
|
|
