Название	МАТЕМАТИЧНИЙ ОПИС ЗГОРТКОВИХ КОДІВ ЗІ ШВИДКІСТЮ R=(n-1)/n
Количество страниц	48
ВУЗ	УКРАЇНСЬКА ДЕРЖАВНА АКАДЕМІЯ ЗВ'ЯЗКУ ім. О. С. ПОПОВА
Год сдачи	2009
Содержание	РЕФЕРАТ Текстова частина дипломної роботи: 48 с., 27 рис., 1 табл., 17 джерел. Об’єкт дослідження – перфоровані та неперфоровані згорткові коди, їх опис. Мета роботи – розробка опису перфорованих згорткових кодів з R=(n-1)/n та еквівалентних їм ЗК. Метод дослідження – математичний аналіз. У дипломній роботі проведено аналіз відомих описів згорткових кодів. Для спрощення та удосконалення опису перфорованих згорткових кодів запрпонований новий метод – опис згорткових кодів за допомогою оператору затримки . Наведено – опис кодера згорткових кодів з R=1/n у вигляді автомата з одним входом і одним виходом. А також – опис кодера ЗК з R=q/(qn) у вигляді автомата з одним входом і одним виходом, і вказаний зв'язок таких кодів з кодами зі швидкістю R=1/n. Проведені перетворення перфорованих згорткових кодів. ПЕРФОРОВАНІ ЗГОРТКОВІ КОДИ, – ОПЕРАТОР ЗАТРИМКИ, ЄКВІВАЛЕНТНА ПОРОДЖУЮЧА МАТРИЦЯ, ПЕРФОРАЦІЙНА МАТРИЦЯ, ПОРОДЖУЮЧІ БАГАТОЧЛЕНИ. Умови одержання дипломної роботи: з дозволу проректора УДАЗ iм. О.С. Попова з навчальної роботи. ЗМІСТ С. ВСТУП . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1 МЕТОДИ ОПИСУ ЗГОРТКОВИХ КОДІВ . . . . . . . . . . . . . . . . . . . . . . . . 9 1.1 Стандартний опис згорткових кодів . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.1.1 Діаграма станів згорткового кодера . . . . . . . . . . . . . . . . . . . . . . . . 9 1.1.2 Гратчаста діаграма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Подання згорткових кодів за допомогою оператору затримки D 1.3 Подання згорткових кодів за допомогою матриць . . . . . . . . 15 1.4 Перфоровані згорткові коди (стандартний опис) . . . . . . . . . . . . . . 17 2 – ОПИС ЗГОРТКОВИХ КОДІВ ЗІ ШВИДКОСТЯМИ R=1/n ТА R= q/(q n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1 Алгебраїчний опис кодера згорткового коду з R=1/n у виді автомата з одним входом і одним виходом. . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Опис згорткового коду з R=1/n у виді автомата з R= q/(q n). Зв´язок згорткових кодів з R=1/n та R= q/(q n). . . . . . . . . . . . . . . . . . . . . . . 30 2.2.1 Перфоровані згорткові коди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3 СВЯЗЬ СВЕРТОЧНЫХ КОДОВ С R= (n–1)/n И ПЕРФОРИРОВАННЫХ СВЕРТОЧНЫХ КОДОВ. . . . . . . . . . . . . . . . . . . . 40 3.1 Перфорированные сверточные коды с R= (n–1)/n и эквивалентные им сверточные коды. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 ВИСНОВКИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 ПЕРЕЛІК ПОСИЛАНЬ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 ВСТУП Згорткові коди були введені Елайсом [7] з Массачусетського технологічного інституту. На відміну від блокових кодів, де кожний символ на виході кодера залежить лише від скінченного числа інформаційних символів на вході кодера, у випадку згорткових кодів символи на виході кодера можуть залежати від нескінченого числа інформаційних символів. В цьому контексті згорткові коди можна розглядати як узагальнення блокових кодів. Розвиток теорії згорткових кодів відбувався в трьох напрямках відповідно до трьох найважливіших методів декодування згорткових кодів: метода граничного декодування [8], метода декодування по максимуму правдоподібності [15] і метода послідовного декодування [14]. Згорткові коди, що виправляють пачки помилок, уперше були запропоновані Хегельбергером [9]. Надалі Вайнер і Еш [11], Препарата [12], Берлекэмп [10], Мессі [13] та ін., базуючись головним чином на теорії матриць, побудували ряд квазиоптимальних кодів, що виправляють пачки помилок і потребують для цього захисний інтервал, близький до мінімально можливого. Якщо на початковому етапі згорткові коди були лише об'єктом теоретичних досліджень, то надалі вони стали застосовуватися спочатку в сполученні з граничним декодуванням у космічному зв'язку , а потім у сполученні з граничним декодуванням у супутникових системах передачі даних, системах морського радіозв'язку та в інших системах. Крім того, аналіз структури згорткових кодів пов'язаний з теорією автоматів. Безсумнівно, що в майбутньому буде спостерігатися подальше поглиблення взаємозв'язку між теоретичними дослідженнями в області згорткових кодів і практичним використанням останніх. Після введення Елайсом згорткових кодів виникло питання про те, які коди (згорткові чи блокові) потенційно кращі. Відповідь на це запитання був даний Вітербі [15], що одержав верхні і нижні границі ймовірності помилки для згорткових кодів і з їхньою допомогою показав, що характеристики оптимальних згорткових кодів, як функції кодового обмеження, краще відповідних характеристик блокових кодів тієї ж довжини. Для одержання цих границь Вітербі використовував алгоритм декодування згорткових кодів, що, як виявилося, діє як алгоритм декодування по максимуму правдоподібності. Цей алгоритм згодом став називатися алгоритмом Вітербі. Застосування алгоритму Вітербі для декодування коротких згорткових кодів дозволяє одержати значний енергетичний виграш в порівнянні з некодованою передачею [16]. Найчастіше використовують коди з швидкістю R=1/2 . При цьому обсяг устаткування декодера мінімальний. Проте кодування з швидкістю R=1/2 потребує двохкратного розширення смуги займаємих частот. В той же час перехід до більш економних кодів зі швидкостями 2/3 і 3/4 ускладнює декодер. Підвищення швидкості коду можливо шляхом періодичного викреслювання (перфорації) символів на виході кодера [17]. Перфоровані коди можна декодувати по гратчастій діаграмі вихідного коду (із швидкістю R=1/2 ), забезпечивши синхронізацію по перфорованих символах. Перфоровані згорткові коди з R=(n-1)/n >1/2 [1] використовуються з метою спрощення декодування згорткових кодів по максимуму правдоподібності і максимуму апостеріорної ймовірності [1–2]. На пошук кодів з хорошими дистанційними властивостями дослідники витрачали великі зусилля. Проте відомі методи опису перфорованих згорткових кодів [3–5] містять помилки [3–4] або є не зовсім точними та громіздкими [5]. У роботі запропонований новий метод опису перфорованих згорткових кодів. Розглядалися згорткові коди: коди з універсальними кодовими генераторами, оптимальними як при R=1/2 (без перфорації), так і при R= 2/3 і 3/4 (з перфорацією); перфоровані коди з генераторами, оптимальними тільки для однієї з швидкостей [6].
Список литературы	ВИСНОВКИ В дипломній роботі досліджені методи опису ЗК з R=(n-1)/n. Запропонований новий метод опису перфорованих кодів, на базі якого побудовані згорткові коди, еквівалентні перфорованим. Цікаво відмітити, що довжина кодового обмеження як у розглянутих перфорованих ЗК, так і у еквивалентних ЗК збігаються. Запропонований метод опису являється менш громіздким. У розділі 1 наведена необхідна інформація про згорткові коди. У розділі 2 наведено – опис кодера з R=1/n у вигляді автомату з одним входом та одним виходом, а також – опис кодера з R=q/(q n) у вигляді автомату з одним входом та одним виходом, та вказаний зв’язок таких кодів з кодами R=1/n.Доказана теорема та виходячий з неї наслідок. Перетворення перфорованих згорткових кодів у еквівалентні їм неперфоровані згорткові коди показано на прикладах у розділі 3. Результати зібрані у таблицю. ПЕРЕЛІК ПОСИЛАНЬ 1. Cain J. B., Clark G. C., Geist J. M. Punctured convolutional codes of rate (n–- 1)/n and simplified maximum likelihood decoding // IEEE Trans. Inform. Theory – 1979. – V. IT–25, – №1. – p. 97 – 100. 2. Berrou C., Glavieux A., Thitimajshima P. Near Shannon limit error-correcting coding and decoding: turbo-codes, IEEE Intern. Conf. on Commun., – 1993. – P. 1064 –1070. 3. Begin G., Haccoun D., Paquin C. High-rate punctured convolutional codes: structure properties and construction technique, IEEE Trans. Commun., – 1989. – V. 37, – P. 1381 – 1385. 4. Hole K. J. Punctured convolutional codes for the 1 - D partial-response channel, IEEE Trans. Inform. Theory, – 1991, – V. 37, № 3. – P. 808 – 817. 5. McEliece R. J. The algebraic theory of convolutional codes, – 1996. – May. – Preprint. 6. Банкет В. Л., Ляхов А. И., Салабай А. В. Спектры весов коротких сверточных кодов // Теория передачи информации по каналам связи: Сб. научных трудов учеб. институтов связи. ТУИС.– Л., 1984 – с. 110 – 119. 7. Elias P., Coding for Noisy Channel, IRE Convention Record, Part 4, 37–46 (1955). 8. Massey J. T., Threshold Decoding, MIT Press, Cambridge Mass., 1963; есть русский перевод: Месси Дж., Пороговое декодирование. – М.: Мир, 1966. – 207 с. 9. Hagelbarger D. W., Recurrent Codes: Easily Macyinized, Burst-Correcting, Binary Codes, BSTJ, 38, 969–984 (1959). 10. Berlecamp E. R., Note on Recurrent Codes, IEEE Trans., IT-10, 257–258 (1964). 11. Wyner A. D., Ash R. B., Analysis of Recurrent Codes, IEEE Trans., IT-9, 143–156 (1963). 12. Preparata F. P., Systematic Constructions of Optimal Linear Recurrent Codes for Burst-Error-Correction, Calcolo, 2, 1–7 (1964). 13. Massey J. L., Inplementation of Burst-Correcting Convolutional Codes, IEEE Trans., IT-11, 416–422 (1965). 14. Wozencraft J. M., Secuential Decoding for Reliable Communication, MIT Research Lab. Of Electronics Tech. Report 325, Cambridge, Mass., 1957. 15. Viterbi A. J., Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm, IEEE Trans., IT-13, 260–269 (1967). 16. Банкет В. Л., Ляхов А. И. Применение сверточных кодов в системах связи с фазовой манипуляцией. // Зарубежная радиоэлектроника, –1981,–№8.–с. 3–23. 17. Банкет В. Л. Сверточные коды в системах передачи информации: Учеб. пособие / Одесск. Электротехн. ин-т связи им А. С. Попова, Одесса, 1986,–57 с.
Цена:	Договорная