Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Жоғары өнімділіктегі алдын ала қате түзету кодтары
High performance forward error correction codes
Ақпарат теориясында турбо кодтар (алғашқыда француз тілінде Turbocodes) – 1990–91 жылдары жасалған, бірақ алғаш рет 1993 жылы жарияланған жоғары өнімділіктегі алдын ала қате түзету (FEC) кодтарының класы. Олар нақты шу деңгейін ескере отырып, сенімді байланыс мүмкін болатын код жылдамдығының теориялық шегі – Шеннон лимитіне жақын тұрған, алғашқы практикалық кодтар болды. Турбо кодтар 3G/4G ұялы байланыста (мысалы, UMTS және LTE) және (аспан кеңістігіндегі) спутниктік байланыста, сондай-ақ деректердің бұзылуына себеп болатын шу болғанда, жолақтық ені немесе жауап уақыты шектеулі байланыс арналары арқылы сенімді ақпарат беруді қамтамасыз етуді көздейтін басқа да қолдануларда қолданылады. Турбо кодтар ұқсас өнімділікті ұсынатын (бірақ патенттелмеген) төмен тығыздықпен тепе-теңдік тексеру (LDPC) кодтарымен бәсекелеседі. "Турбо код" атауы турбо кодты декодтау кезінде қолданылатын кері байланыс циклінен туындады, ол қозғалтқышты турбо зарядтау үшін қолданылатын газ шығарудың кері байланысына ұқсас болды. Хагенауэр турбо код термині қате қолданылған деп санайды, себебі кодтау процесінде кері байланыс болмайды.
In information theory, turbo codes (originally in French Turbocodes) are a class of high performance forward error correction (FEC) codes developed around 1990–91, but first published in 1993. They were the first practical codes to closely approach the maximum channel capacity or Shannon limit, a theoretical maximum for the code rate at which reliable communication is still possible given a specific noise level. Turbo codes are used in 3G/4G mobile communications (e. g., in UMTS and LTE) and in (deep space) satellite communications as well as other applications where designers seek to achieve reliable information transfer over bandwidth or latency constrained communication links in the presence of data corrupting noise. Turbo codes compete with low density parity check (LDPC) codes, which provide similar performance (but were patent free). The name "turbo code" arose from the feedback loop used during normal turbo code decoding, which was analogized to the exhaust feedback used for engine turbocharging. Hagenauer has argued the term turbo code is a misnomer since there is no feedback involved in the encoding process.
Тарих
Турбо кодтарға арналған негізгі патенттік өтінім 1991 жылдың 23 сәуірінде тіркелген. Патенттік өтінімде Клод Берру турбо кодтардың жалғыз ойлап табушысы ретінде көрсетілген. Патентті тіркеу нәтижесінде бірнеше патент алынды, оның ішінде 2013 жылдың 29 тамызында мерзімі біткен АҚШ патенті 5,446,747. Турбо кодтар туралы алғашқы жарияланған мақала – "Шаннон шегіне жуық қате түзетуді кодтау және декодтау: Турбо кодтар". Бұл мақала 1993 жылы IEEE Халықаралық коммуникациялар конференциясының материалдарында жарияланды. 1993 жылғы мақала кеңістік шектеулеріне байланысты біріктірілген үш жекелеген ұсыныстан тұрды. Біріктіру салдарынан мақала үш авторды көрсетті: Берру, Главикс және Титимажишима (Télécom Bretagne, бұрынғы ENST Bretagne, Франция). Алайда, бастапқы патенттік өтінімнен Берру турбо кодтардың жалғыз ойлап табушысы екені және мақаланың басқа авторлары негізгі түсініктерден өзге материалдарды қосқандығы анық көрінеді. Турбо кодтар енгізілген кезде революциялық болды, сондықтан кодтау саласындағы көптеген сарапшылар жарияланған нәтижелерге күмәнданды. Нәтижелер расталғаннан кейін кодтау әлемінде шағын революция болды, ол көптеген басқа итеративтік сигналды өңдеу түрлерін зерттеуге әкелді. Турбо кодтардың алғашқы класы – параллель конкатенацияланған конволюциялық код (PCCC). 1993 жылы түпнұсқа параллель турбо кодтар енгізілгеннен бері, турбо кодтардың көптеген басқа кластары ашылды, соның ішінде сериялық түрлері, сериялық конкатенацияланған конволюциялық кодтар және қайталап жинақтау кодтары. Итеративтік турбо декодтау әдістері сондай-ақ дәстүрлі FEC жүйелеріне қолданылды, оның ішінде Рид-Соломон түзетілген конволюциялық кодтар, бірақ бұл жүйелер итеративтік декодерлерді іске асыру үшін тым күрделі. Турбо теңдеу де турбо кодтау тұжырымынан туындады. Турбо кодтардан басқа, Берру рекурсивті жүйелі конволюциялық (RSC) кодтарын да ойлап тапты, олар патентте сипатталған турбо кодтардың мысалдық іске асырылуында қолданылады. RSC кодтарын пайдаланатын турбо кодтар RSC кодтарын пайдаланбайтын турбо кодтардан жақсы нәтижелер көрсетеді. Турбо кодтарға дейін ең жақсы құрылымдар – сыртқы Рид-Соломон қатесін түзету кодына негізделген, ішкі Витерби декодталған қысқа шектеу ұзындығы конволюциялық кодымен біріктірілген сериялық конкатенацияланған кодтар, сондай-ақ RSV кодтары деп белгілі кодтар болды. Кейінгі мақаласында Берру "80-ші жылдардың соңында ықтималдық өңдеуге қызығушылық танытқан G. Battail, J. Hagenauer және P. Hoeher-дің интуициясына" ризашылық білдірді. Ол сондай-ақ "Р. Галлагер және М. Таннер кодтау және декодтау техникаларын ойлап тапқан, олардың жалпы принциптері тығыз байланысты", дегенмен сол кезде қажетті есептеулер практикалық емес еді деп қосты.
The fundamental patent application for turbo codes was filed on 23 April 1991. The patent application lists Claude Berrou as the sole inventor of turbo codes. The patent filing resulted in several patents including US Patent 5,446,747, which expired 29 August 2013. The first public paper on turbo codes was "Near Shannon Limit Error correcting Coding and Decoding: Turbo codes". This paper was published 1993 in the Proceedings of IEEE International Communications Conference. The 1993 paper was formed from three separate submissions that were combined due to space constraints. The merger caused the paper to list three authors: Berrou, Glavieux, and Thitimajshima (from Télécom Bretagne, former ENST Bretagne, France). However, it is clear from the original patent filing that Berrou is the sole inventor of turbo codes and that the other authors of the paper contributed material other than the core concepts. Turbo codes were so revolutionary at the time of their introduction that many experts in the field of coding did not believe the reported results. When the performance was confirmed a small revolution in the world of coding took place that led to the investigation of many other types of iterative signal processing. The first class of turbo code was the parallel concatenated convolutional code (PCCC). Since the introduction of the original parallel turbo codes in 1993, many other classes of turbo code have been discovered, including serial versions serial concatenated convolutional codes and repeat accumulate codes. Iterative turbo decoding methods have also been applied to more conventional FEC systems, including Reed–Solomon corrected convolutional codes, although these systems are too complex for practical implementations of iterative decoders. Turbo equalization also flowed from the concept of turbo coding. In addition to turbo codes, Berrou also invented recursive systematic convolutional (RSC) codes, which are used in the example implementation of turbo codes described in the patent. Turbo codes that use RSC codes seem to perform better than turbo codes that do not use RSC codes. Prior to turbo codes, the best constructions were serial concatenated codes based on an outer Reed–Solomon error correction code combined with an inner Viterbi decoded short constraint length convolutional code, also known as RSV codes. In a later paper, Berrou gave credit to the intuition of "G. Battail, J. Hagenauer and P. Hoeher, who, in the late 80s, highlighted the interest of probabilistic processing." He adds "R. Gallager and M. Tanner had already imagined coding and decoding techniques whose general principles are closely related," although the necessary calculations were impractical at that time.
Биттерді табу үшін гипотезаларды шешу
Турбо кодтардың негізгі жаңалығы – екі декодер арасындағы қарама-қайшылықтарды шешу үшін ықтималдық деректерін қолдану болып табылады. Екі конволюциялық декодердің әрқайсысы пайдалы жүктеме кіші блогындағы m биттің үлгісі үшін гипотеза (туынды ықтималдықтармен бірге) құрайды. Гипотезалық бит үлгілері салыстырылады, егер олар өзгеше болса, декодерлер гипотезадағы әр бит үшін туынды ықтималдықтарды алмасады. Әр декодер екінші декодерден алынған ықтималдық бағалауларын пайдаланып, пайдалы жүктемедегі биттер үшін жаңа гипотеза жасайды. Содан кейін олар осы жаңа гипотезаларды салыстырады. Бұл итеративтік процесс екі декодердің де жүктемедегі m бит үлгісі үшін бірдей гипотезаға келуіне дейін, әдетте 15-18 цикл ішінде жалғасады. Бұл процесті кроссворд немесе судоку сияқты өзара байланысты сөзжұмбақтарды шешумен салыстыруға болады. Толық емес, мүмкін бұрмаланған кроссвордты қарастырайық. Екі сөзжұмбақ шешуші (декодерлер) оны шешуге тырысады: біреуі тек "төменге" (паритет биттері) берілген нұсқауларды, ал екіншісі тек "қарсыға" берілген нұсқауларды біледі. Бастапқыда, екі шешуші де өздерінің нұсқауларына жауаптарды (гипотезаларды) болжайды, сонымен қатар әр әріпке (пайдалы жүктеме биті) қаншалықты сенімді екендерін жазып алады. Содан кейін олар жауаптар мен сенімділік деңгейлерін алмасып, қайда және қалай ерекшеленетінін анықтап, салыстырады. Осы жаңа мәліметтерге сүйене отырып, олар жаңартылған жауаптар мен сенімділік деңгейлерін жасайды, осы процесті бір шешімге келгенше қайталайды.
The key innovation of turbo codes is how they use the likelihood data to reconcile differences between the two decoders. Each of the two convolutional decoders generates a hypothesis (with derived likelihoods) for the pattern of m bits in the payload sub block. The hypothesis bit patterns are compared, and if they differ, the decoders exchange the derived likelihoods they have for each bit in the hypotheses. Each decoder incorporates the derived likelihood estimates from the other decoder to generate a new hypothesis for the bits in the payload. Then they compare these new hypotheses. This iterative process continues until the two decoders come up with the same hypothesis for the m bit pattern of the payload, typically in 15 to 18 cycles. An analogy can be drawn between this process and that of solving cross reference puzzles like crossword or sudoku. Consider a partially completed, possibly garbled crossword puzzle. Two puzzle solvers (decoders) are trying to solve it: one possessing only the "down" clues (parity bits), and the other possessing only the "across" clues. To start, both solvers guess the answers (hypotheses) to their own clues, noting down how confident they are in each letter (payload bit). Then, they compare notes, by exchanging answers and confidence ratings with each other, noticing where and how they differ. Based on this new knowledge, they both come up with updated answers and confidence ratings, repeating the whole process until they converge to the same solution.
Өнер көрсету
Турбо кодтар арнада кодтың кездейсоқ сипатталуының және физикалық жүзеге асырылатын декодтау құрылымының үйлесімді комбинациясының арқасында жақсы жұмыс істейді. Турбо кодтар қателік еденіне ұшырайды.
Turbo codes perform well due to the attractive combination of the code's random appearance on the channel together with the physically realisable decoding structure. Turbo codes are affected by an error floor.
Бейес формуласы
Жасанды интеллект көзқарасынан, турбо кодтарды Байес желілеріндегі циклдық сенім таратудың бір мысалы ретінде қарастыруға болады.
From an artificial intelligence viewpoint, turbo codes can be considered as an instance of loopy belief propagation in Bayesian networks.