Кіріспе
Конволюцияны қолданатын қателерді түзету кодының түрі. Телекоммуникацияда конволюциялық код – дерек ағынына Бульдік полиномдық функцияны жылжыту арқылы паритеттік символдарды жасайтын қателерді түзету кодының бір түрі. Бұл жылжыту енкодердің дерекке «конволюциясын» білдіреді, содан «конволюциялық кодтау» термині пайда болды. Конволюциялық кодтардың жылжымалы сипаты уақыт бойынша өзгермейтін торды қолдану арқылы торды декодтауды жеңілдетеді. Уақыт бойынша инвариантты торды декодтау конволюциялық кодтардың максималды ықтималдылықпен жұмсақ шешімдерді декодтауын қамтамасыз етеді, бұл олардың күрделілігін ақылға қонымды деңгейде ұстайды. Экономикалық тұрғыдан тиімді максималды ықтималдылықпен жұмсақ шешімдерді декодтау мүмкіндігі – конволюциялық кодтардың маңызды артықшылықтарының бірі. Бұл классикалық блок кодтарынан өзгеше, олар әдетте уақыт бойынша өзгеретін тормен көрсетіледі және демек, көбінесе қатты шешімдермен декодталады. Конволюциялық кодтар көбінесе базалық код жылдамдығы және енкодердің тереңдігі (немесе жады) арқылы сипатталады. Базалық код жылдамдығы әдетте , мұнда n – кіріс деректерінің жылдамдығы, ал k – шығыс арнасының кодталған ағынының дерек жылдамдығы. n, k-ден кіші, себебі арналық кодтау кіріс биттеріне артық ақпарат қосады. Жады жиі «шектеу ұзындығы» K деп аталады, мұнда шығыс ағымдағы кіріс пен алдыңғы кірістердің функциясы болып табылады. Тереңдік сондай-ақ полиномдағы жад элементтерінің саны v немесе енкодердің ең көп мүмкін күйлер саны ретінде де көрсетілуі мүмкін (әдетте: ). Конволюциялық кодтар көбінесе үздіксіз деп сипатталады. Алайда, конволюциялық кодтардың үздіксіз емес, кездейсоқ блок ұзындығы бар деп айтуға болады, өйткені нақты әлемдегі конволюциялық кодтау деректер блогында жүзеге асырылады. Конволюциялық кодталған блок кодтары көбінесе тоқтатуды қолданады. Конволюциялық кодтардың кездейсоқ блок ұзындығы классикалық блок кодтарынан өзгеше, олардың блок ұзындығы алгебралық қасиеттерімен анықталады. Конволюциялық кодтың жылдамдығы көбінесе символдарды пункциялау арқылы өзгертіледі. Мысалы, «аналық» код жылдамдығы бар конволюциялық код, код символдарының бір бөлігін жібермеу арқылы, мысалы, жоғары жылдамдыққа дейін пункциялануы мүмкін. Пункцияланған конволюциялық кодтың өнімділігі, әдетте, жіберілген паритеттің мөлшерімен пропорционалды. Конволюциялық кодтарда экономикалық жұмсақ шешімдерді декодтау мүмкіндігі, сондай-ақ конволюциялық кодтардың блок ұзындығы мен код жылдамдығының икемділігі оларды цифрлық байланыс үшін өте танымал етеді.
In telecommunication, a convolutional code is a type of error correcting code that generates parity symbols via the sliding application of a boolean polynomial function to a data stream. The sliding application represents the 'convolution' of the encoder over the data, which gives rise to the term 'convolutional coding'. The sliding nature of the convolutional codes facilitates trellis decoding using a time invariant trellis. Time invariant trellis decoding allows convolutional codes to be maximum likelihood soft decision decoded with reasonable complexity. The ability to perform economical maximum likelihood soft decision decoding is one of the major benefits of convolutional codes. This is in contrast to classic block codes, which are generally represented by a time variant trellis and therefore are typically hard decision decoded. Convolutional codes are often characterized by the base code rate and the depth (or memory) of the encoder The base code rate is typically given as , where n is the raw input data rate and k is the data rate of output channel encoded stream. n is less than k because channel coding inserts redundancy in the input bits. The memory is often called the "constraint length" K, where the output is a function of the current input as well as the previous inputs. The depth may also be given as the number of memory elements v in the polynomial or the maximum possible number of states of the encoder (typically: ). Convolutional codes are often described as continuous. However, it may also be said that convolutional codes have arbitrary block length, rather than being continuous, since most real world convolutional encoding is performed on blocks of data. Convolutionally encoded block codes typically employ termination. The arbitrary block length of convolutional codes can also be contrasted to classic block codes, which generally have fixed block lengths that are determined by algebraic properties. The code rate of a convolutional code is commonly modified via symbol puncturing. For example, a convolutional code with a 'mother' code rate may be punctured to a higher rate of, for example, simply by not transmitting a portion of code symbols. The performance of a punctured convolutional code generally scales well with the amount of parity transmitted. The ability to perform economical soft decision decoding on convolutional codes, as well as the block length and code rate flexibility of convolutional codes, makes them very popular for digital communications.
Тарих
Конволюциялық кодтарды 1955 жылы Питер Элиас енгізді. Конволюциялық кодтарды есептеу және кідіріс шығынымен кез келген сапада декодтауға болады деп есептелді. 1967 жылы Эндрю Витерби конволюциялық кодтарды уақыт бойынша өзгермейтін торлы декодерлерді пайдаланып, Витерби алгоритмі арқылы ақылға қонымды күрделілікпен максималды ықтималдықпен декодтауға болатынын анықтады. Кейін BCJR декодтау алгоритмі сияқты басқа торлы декодер алгоритмдері де әзірленді. Рекурсивті жүйелі конволюциялық кодтарды Клод Берру шамамен 1991 жылы ойлап тапты. Бұл кодтар итеративті өңдеу үшін, соның ішінде турбо кодтар сияқты тізбектелген кодтарды өңдеу үшін ерекше пайдалы болды. "Конволюциялық" терминологияны қолданғанда, классикалық конволюциялық кодты шекті импульстік жауап (FIR) сүзгісі ретінде қарастыруға болады, ал рекурсивті конволюциялық кодты шексіз импульстік жауап (IIR) сүзгісі ретінде қарастыруға болады.
Конвольляциялық кодтар пайдаланылған жағдайда
Конвольциялық кодтар цифрлық бейне, радио, ұялы байланыс (мысалы, GSM, GPRS, EDGE және 3G желілерінде (3GPP Release 7 дейін)) және спутниктік байланыс сияқты көптеген қолданыстарда сенімді деректерді беруді қамтамасыз ету үшін кеңінен қолданылады. Бұл кодтар көбінесе қатты шешім қабылдау кодтарымен, әсіресе Рид-Соломон кодымен біріктіріледі. Турбо кодтары пайда болғанға дейін мұндай құрылымдар ең тиімді болып саналды және Шеннон лимитіне ең жақын нәтижелерді көрсетті.
Еркін қашықтық және қате таралуы
Еркін қашықтық (d) – әр түрлі кодталған тізбектер арасындағы ең кішкентай Хамминг қашықтығы. Конволюциялық кодтың түзету мүмкіндігі (t) – кодтың түзете алатын қателер саны. Оны келесідей есептеуге болады:
Конволюциялық код блоктарды пайдаланбай, үздіксіз бит ағынын өңдейтіндіктен, t мәні бір-біріне жақын орналасқан қателер санына қатысты қолданылады. Яғни, t қателерінің бірнеше тобы алыс болған жағдайда түзетілуі мүмкін. Еркін қашықтықты конволюциялық декодердің шығысындағы қателік "жарылысының" ең аз ұзындығы деп түсінуге болады. Қателердің "жарылыс" түрінде пайда болу фактісі конволюциялық кодты ішкі код ретінде пайдаланатын біріктірілген кодты жобалау кезінде ескерілуі керек. Бұл мәселенің танымал шешімі – конволюциялық кодтаудан бұрын деректерді араластыру, сонда сыртқы блок (әдетте Рид-Соломон) коды көптеген қателерді түзете алады.
Конвольляциялық кодтарды шешу
Конвольциялық кодтарды декодтау үшін бірнеше алгоритмдер бар. k-ның салыстырмалы түрде кіші мәндері үшін Витерби алгоритмі әмбебап түрде қолданылады, себебі ол максималды ықтималдықпен жұмыс істейді және жоғары деңгейде параллельдеуге мүмкіндік береді. Сондықтан Viterbi декодерлерін VLSI аппараттық құралдарында және SIMD нұсқаулар жиынтығы бар процессорлардағы бағдарламалық жасақтамада жүзеге асыру оңай. Ұзын шектеу ұзындығы кодтарын декодтау үшін бірнеше тізбекті декодтау алгоритмдерінің кез келгенін қолдануға болады, олардың ішінде Фано алгоритмі ең белгілісі. Витерби декодтаудан айырмашылығы, тізбекті декодтау максималды ықтималдық емес, бірақ оның күрделілігі шектеу ұзындығымен салыстырмалы түрде аз өседі, бұл күшті, ұзын шектеу ұзындығы кодтарын пайдалануға мүмкіндік береді. Мұндай кодтар 1970 жылдардың басында Юпитер және Сатурн планеталарына жіберілген «Пионер» бағдарламасында қолданылды, бірақ олардың орнына қысқа, Витерби декодталған кодтар қолданыла бастады, әдетте үлкен Рид-Соломон қателерді түзету кодтарымен біріктіріледі, бұл жалпы бит қателіктерінің көрсеткішін төмендетіп, өте төмен қалдық анықталмаған қателік деңгейін қамтамасыз етеді. Viterbi және тізбекті декодтау алгоритмдерінің екеуі де нақты шешімдерді қайтарады: ең ықтимал код сөзін құрайтын биттер. Soft output Viterbi алгоритмін қолдану арқылы әр бит үшін шамамен сенімділік өлшемін қосуға болады. Әр бит үшін максималды апостериорлы (MAP) жұмсақ шешімдерді алу үшін BCJR алгоритмін қолдануға болады.
Танымал ыдырау кодтары
Шындығында, ғылыми зерттеулер барысында алынған, алдын ала анықталған конволюциялық кодтардың құрылымдары индустрияда қолданылады. Бұл қателердің көбеюіне себеп болатын апаттық конволюциялық кодтарды таңдау мүмкіндігімен байланысты. Әсіресе танымал Витерби декодерленген конволюциялық код, кем дегенде "Вояджер" бағдарламасынан бері қолданылып келеді, оның шектеу ұзындығы K 7, ал жылдамдығы r 1/2 құрайды. "Mars Pathfinder", "Mars Exploration Rover" және Сатурнға жіберілген "Cassini" ғарыш зонды K 15 және 1/6 жылдамдығын пайдаланады; бұл код, "Voyager" миссиясы кодтарымен салыстырғанда, декодтау күрделілігі 256 есе артып, қарапайым кодқа қарағанда шамамен 2 дБ жақсы нәтиже береді. Конволюциялық код, шектеу ұзындығы 2 және жылдамдығы 1/2 болатын, GSM жүйесінде қателерді түзету тәсілі ретінде қолданылады.
Пункциялы ыдырау кодтары
Кез келген код жылдамдығы бар конволюциялық кодты полиномдарды таңдау арқылы жобалауға болады; алайда, практикада қажетті код жылдамдығына қол жеткізу үшін көбінесе перфорациялау процедурасы қолданылады. Перфорациялау – бұл "базалық" төмен жылдамдықты (мысалы, 1/n) кодтан m/n жылдамдықты код жасауға арналған техника. Бұл кодтаушының шығысынан кейбір биттерді жою арқылы жүзеге асырылады. Биттер перфорациялық матрица бойынша жойылады. Ең көп қолданылатын перфорациялық матрицалар төменде келтірілген:
Код жылдамдығы | Перфорациялық матрица | Бос қашықтық (NASA стандарты бойынша K=7 конволюциялық коды үшін)
---|---|---
1/2 (Перфорация жоқ) | 1 1 | 10
2/3 | 1 0 1 1 | 6
3/4 | 1 0 1 1 1 0 | 5
5/6 | 1 0 1 0 1 1 1 0 1 0 | 4
7/8 | 1 0 0 0 1 0 1 1 1 1 1 0 1 0 | 3
Мысалы, егер жоғарыдағы кестеден тиісті матрицаны пайдаланып 2/3 жылдамдықты код жасағымыз келсе, біз базалық кодтаушының шығысын алып, бірінші тармақтан әрбір бірінші битті және екінші тармақтан әрбір битті жіберуіміз керек. Жіберудің нақты реті тиісті байланыс стандартымен анықталады. Перфорацияланған конволюциялық кодтар спутниктік байланыста кеңінен қолданылады, мысалы, INTELSAT жүйелерінде және Цифрлық бейне хабар таратуда. Перфорацияланған конволюциялық кодтарды "перфорацияланған" деп те атайды.
Турбо кодтар: конвольсиялық кодтарды алмастыру
Қарапайым Витерби декодталған конволюциялық кодтар енді турбо кодтарға жол береді, бұл Шеннон теоремасымен белгіленген теориялық шектерге жақын келетін, қайталамалы қысқа конволюциялық кодтардың жаңа класы. Олар бірдей өнімділікке қол жеткізу үшін қажет болатын ұзақ конволюциялық кодтардағы Витерби алгоритміне қарағанда әлдеқайда аз декодтау күрделілігін қамтамасыз етеді. Сыртқы алгебралық кодпен (мысалы, Рид-Соломон) біріктіру турбо кодтардың дизайнындағы қателік едендері мәселесін шешеді.
Жарияланымдар
Фрэнсис, Майкл. "Витерби декодер блогының декодтаулауы, торлық аяқтау және құйрықты тістеу". Xilinx XAPP551 v2 нұсқасы. 0, ДД (2005): 1–21. Чен, Цинчунь, Вай Хо Моу және Пингзи Фан. "Рекурсивті конволюциялық кодтар және олардың қолданылуы туралы жаңа нәтижелер". Ақпарат теориясы жөніндегі семинар, 2006. ITW'06 Ченгду. IEEE. IEEE, 2006. Фибиг, Ю. К. және Патрик Робертсон. "Жұмсақ шешім және тез жиілік ауыстыру жүйелерінде конволюциялық, турбо және Рид-Соломон кодтарымен декодтау және жою". IEEE байланыс транзакциялары 47.11 (1999): 1646–1654. Бхаскар, Видхьячаран және Лори Л. Джойнер. "Мүжілген конволюциялық кодтардың асинхронды CDMA байланыстарындағы өнімділігі, тамаша фазалық бақылау шарттарында". Компьютерлер және электр инженериясы 30.8 (2004): 573–592. Модестино, Дж. және Шо Муи. "Рисиандық жоғалу арнасындағы конволюциялық кодтың өнімділігі". IEEE байланыс транзакциялары 24.6 (1976): 592–606. Чен, Ю Лонг және Чэ Хо Вэй. "Рисиандық жоғалу арналарында MPSK-мен конволюциялық кодтардың өнімділігін бағалау". IEE іс-қағаздары F Байланыс, радар және сигналды өңдеу. 134-том. 2-нөмір. IET, 1987.