Қателерді түзету кодтары және шулы каналдар арқылы деректерді беру

Кіріспе

Шулы байланыс арналары арқылы деректердегі қателерді бақылау схемасы

Есептеу, телекоммуникация, ақпараттық теория және кодтау теориясында алдын ала қателерді түзету (FEC) немесе арналық кодтау – сенімсіз немесе шулы байланыс арналары арқылы деректерді берудегі қателерді бақылау үшін қолданылатын техника. Басты идеясы – жіберуші хабарламаны артық мөлшерде кодтайды, көбінесе қателерді түзету кодын немесе қателерді түзету кодын (ECC) пайдаланады. Артық мөлшердегі код қабылдаушыға хабарламаның кез келген жерінде туындаған қателерді анықтауға ғана емес, сонымен қатар шектеулі сандағы қателерді түзетуге мүмкіндік береді. Сондықтан қайта жіберуді сұрау үшін кері арна қажет болмауы мүмкін. Бұл үшін алдын ала арнаның жолақтығы тұрақты түрде жоғары болуы керек. Американдық математик Ричард Хамминг осы саланың негізін қалаушы болды және 1950 жылы алғашқы қателерді түзету кодын ойлап тапты: Хамминг (7,4) кодын. Бұл бір биттік қателерді түзету және 2 биттік қателерді анықтау мүмкіндігін береді. Хамминг кодтары тек сенімді бір деңгейлі жад ұяшықтары (SLC) NAND үшін қолайлы. Жоғары тығыздықпен сақталатын көп деңгейлі жад ұяшықтары (MLC) NAND көп биттік түзетуге арналған ECC-ді, мысалы BCH немесе Reed–Solomon кодын пайдалана алады. NOR Flash әдетте қателерді түзетуді қолданбайды, яғни әрбір кіріс және шығыс сигналы үшін бір немесе нөл битіне сәйкес келе ме деген шешім қабылданады. Керісінше, конволюциялық кодтар әдетте Viterbi, MAP немесе BCJR алгоритмдері сияқты жұмсақ шешімдер алгоритмдерін қолдана отырып, (дискреттелген) аналогты сигналдарды өңдейді және қатты шешімдерді кодтауға қарағанда қателерді түзетудің жоғары тиімділігін қамтамасыз етеді. Көптеген классикалық блок кодтары шекті өрістердің алгебралық қасиеттерін қолданады. Сондықтан классикалық блок кодтары көбінесе алгебралық кодтар деп аталады. Қателерді анықтау немесе түзету қабілетін анықтайтын классикалық блок кодтарынан айырмашылығы, LDPC кодтары сияқты көптеген заманауи блок кодтары мұндай кепілдіктер бермейді. Оның орнына, қазіргі заманғы кодтар биттік қателік деңгейі бойынша бағаланады. Көптеген алдын ала қателерді түзету кодтары тек биттердің ауысуын түзетуге қабілетті, бірақ биттерді қосуға немесе жоюға емес. Мұндай жағдайда Хэмминг қашықтығы биттік қателік деңгейін өлшеуге қолайлы тәсіл болып табылады. Маркерлік кодтар және Су белгілері кодтары сияқты кейбір алдын ала қателерді түзету кодтары биттерді қосу және жою қателерін түзетуге арналған. Мұндай кодтарды қолданған кезде биттік қателік деңгейін өлшеу үшін Левенштейн қашықтығы тиімдірек болады.

In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The central idea is that the sender encodes the message in a redundant way, most often by using an error correction code or error correcting code (ECC). The redundancy allows the receiver not only to detect errors that may occur anywhere in the message, but often to correct a limited number of errors. Therefore a reverse channel to request re transmission may not be needed. The cost is a fixed, higher forward channel bandwidth. The American mathematician Richard Hamming pioneered this field in the 1940s and invented the first error correcting code in 1950: the Hamming (7,4) code. This provides single bit error correction and 2 bit error detection. Hamming codes are only suitable for more reliable single level cell (SLC) NAND. Denser multi level cell (MLC) NAND may use multi bit correcting ECC such as BCH or Reed–Solomon. NOR Flash typically does not use any error correction. which means that for every input and output signal a hard decision is made whether it corresponds to a one or a zero bit. In contrast, convolutional codes are typically decoded using soft decision algorithms like the Viterbi, MAP or BCJR algorithms, which process (discretized) analog signals, and which allow for much higher error correction performance than hard decision decoding. Nearly all classical block codes apply the algebraic properties of finite fields. Hence classical block codes are often referred to as algebraic codes. In contrast to classical block codes that often specify an error detecting or error correcting ability, many modern block codes such as LDPC codes lack such guarantees. Instead, modern codes are evaluated in terms of their bit error rates. Most forward error correction codes correct only bit flips, but not bit insertions or bit deletions. In this setting, the Hamming distance is the appropriate way to measure the bit error rate. A few forward error correction codes are designed to correct bit insertions and bit deletions, such as Marker Codes and Watermark Codes. The Levenshtein distance is a more appropriate way to measure the bit error rate when using such codes.

Кодтық жылдамдық және сенімділік пен деректік жылдамдық арасындағы компромисс

ЭЦК-ның негізгі принципі – декодерге хабарды жіберуші кодтаған нағыз мәліметті табуға көмектесу үшін артық биттерді қосу. Белгілі бір ЭЦК жүйесінің кодтық жылдамдығы берілген байланыс пакетіндегі ақпараттық биттер санының, жалпы биттер санына (яғни ақпараттық және артық биттерге) қатынасы ретінде анықталады. Сондықтан кодтық жылдамдық – нақты сан болады. Нөлге жақын төмен кодтық жылдамдық жақсы нәтижеге жету үшін көптеген артық биттерді пайдаланатын күшті кодты білдіреді, ал 1-ге жақын жоғары кодтық жылдамдық әлсіз кодты білдіреді. Ақпаратты қорғайтын артық биттерді оларды қорғауға тырысатын бірдей байланыс ресурстарын пайдалана отырып жіберу керек. Бұл сенімділік пен деректерді беру жылдамдығы арасындағы негізгі тепе-теңдікке әкеледі. Бір жағынан, күшті код (төмен кодтық жылдамдықпен) қабылдағыштағы SNR-ді (сигналдың шуға қатынасы) айтарлықтай арттырып, бит қатесінің деңгейін төмендетеді, бірақ тиімді деректерді беру жылдамдығы төмендейді. Екінші жағынан, ЭЦК қолданбастан (яғни кодтық жылдамдық 1-ге тең болғанда) ақпаратты жіберу үшін арнаның барлық мүмкіндіктерін пайдаланады, бірақ биттерге қосымша қорғаныссыз қалдырады. Қызықты сұрақ: декодтау қатесінің деңгейі мардымсыз ЭЦК ақпаратты жіберу жағынан қаншалықты тиімді болуы мүмкін? Бұл сұраққа Клод Шеннон өзінің екінші теоремасымен жауап берді, онда арнаның сыйымдылығы – кез келген ЭЦК-ның қатесі нөлге жақындағанда қол жеткізе алатын ең жоғары бит жылдамдығы делінеді. Оның дәлелі Гаусс кездейсоқ кодтауға негізделген, ол нақты қолдануларға жарамсыз. Шеннонның жұмысы берген жоғарғы шек, соңғы нәтижеге жақындауға тырысатын ЭЦК-ны жобалаудағы ұзақ ізденіске түрткі болды. Бүгінгі таңдағы әртүрлі кодтар Шеннон шегіне жуық нәтижелерге қол жеткізе алады. Алайда, сыйымдылыққа қол жеткізе алатын ЭЦК-ны жүзеге асыру әдетте өте күрделі. Ең танымал ЭЦК-лар өнімділік пен есептеу күрделілігі арасындағы тепе-теңдікті ұсынады. Әдетте, олардың параметрлері сценарийге байланысты оңтайландырылатын мүмкін кодтық жылдамдықтардың диапазонын қамтиды. Әдетте, бұл оңтайландыру деректерді беру жылдамдығына тигізетін әсерді азайта отырып, кодтау қатесінің төмен болу ықтималдығына қол жеткізу үшін жасалады. Кодтық жылдамдықты оңтайландырудың тағы бір критерийі – байланыстың энергиялық шығындарына байланысты төмен қателік деңгейі мен қайта жіберулер санын теңестіру.

The fundamental principle of ECC is to add redundant bits in order to help the decoder to find out the true message that was encoded by the transmitter. The code rate of a given ECC system is defined as the ratio between the number of information bits and the total number of bits (i. e., information plus redundancy bits) in a given communication package. The code rate is hence a real number. A low code rate close to zero implies a strong code that uses many redundant bits to achieve a good performance, while a large code rate close to 1 implies a weak code. The redundant bits that protect the information have to be transferred using the same communication resources that they are trying to protect. This causes a fundamental tradeoff between reliability and data rate. In one extreme, a strong code (with low code rate) can induce an important increase in the receiver SNR (signal to noise ratio) decreasing the bit error rate, at the cost of reducing the effective data rate. On the other extreme, not using any ECC (i. e., a code rate equal to 1) uses the full channel for information transfer purposes, at the cost of leaving the bits without any additional protection. One interesting question is the following: how efficient in terms of information transfer can an ECC be that has a negligible decoding error rate? This question was answered by Claude Shannon with his second theorem, which says that the channel capacity is the maximum bit rate achievable by any ECC whose error rate tends to zero: His proof relies on Gaussian random coding, which is not suitable to real world applications. The upper bound given by Shannon's work inspired a long journey in designing ECCs that can come close to the ultimate performance boundary. Various codes today can attain almost the Shannon limit. However, capacity achieving ECCs are usually extremely complex to implement. The most popular ECCs have a trade off between performance and computational complexity. Usually, their parameters give a range of possible code rates, which can be optimized depending on the scenario. Usually, this optimization is done in order to achieve a low decoding error probability while minimizing the impact to the data rate. Another criterion for optimizing the code rate is to balance low error rate and retransmissions number in order to the energy cost of the communication.

Жеткізуді жақсарту үшін біріктірілген ЭКК кодтары

Классикалық (алгебралық) блок кодтары және конволюциялық кодтар жиі біріктірілген кодтау схемаларында қолданылады, онда қысқа шектеу ұзындығы бар Витерби декодталған конволюциялық код көп бөлік жұмысты атқарады, ал үлкен символ өлшемі және блок ұзындығы бар блок коды (әдетте Рид-Соломон) конволюциялық декодер жасаған қателерді "түзетуге" көмектеседі. Осы қателерді түзету кодтарының отбасысын бір рет өңдеу арқылы өте төмен қате деңгейлеріне қол жеткізуге болады, бірақ ұзақ қашықтықтағы беріліс жағдайларында (мысалы, терең ғарышта) итеративті декодтау ұсынылады. Біріктірілген кодтар спутниктік және терең ғарыш байланыстарында стандартты практика болып табылады, өйткені Вояджер-2 алғаш рет 1986 жылы Уранмен кездескен кезде осы техниканы қолданды. Галилео ғарыш кемесі антеннаның істен шығуына байланысты туындаған өте жоғары қате деңгейлерін компенсациялау үшін итеративті біріктірілген кодтарды пайдаланды.

Турбо кодтары

Турбо-кодтау – екі немесе одан көп салыстырмалы түрде қарапайым конволюциялық кодтарды және араластырғышты біріктіретін итеративті жұмсақ кодтау схемасы, бұл Шеннон шегіне жақын өнімділік көрсете алатын блок кодты құрайды. LDPC кодтары практикалық қолданысқа енгенге дейін турбо-кодтау қолданысқа алынған, бірақ қазір олардың өнімділігі шамалас. Турбо-кодтаудың алғашқы коммерциялық қолданыстарының бірі – Qualcomm компаниясы әзірлеген және Verizon Wireless, Sprint және басқа операторлар сатқан CDMA2000 1x (TIA IS 2000) цифрлық ұялы байланыс технологиясы. Ол сондай-ақ, әсіресе интернетке қол жеткізу үшін CDMA2000 1x технологиясының дамуында, 1xEV DO (TIA IS 856) үшін де қолданылады. 1x сияқты, EV DO-ны да Qualcomm әзірледі және оны Verizon Wireless, Sprint және басқа операторлар сатады (Verizon компаниясы 1xEV DO-ны «Broadband Access» деп, ал Sprint компаниясы тұтынушылар үшін «Power Vision», бизнес үшін «Mobile Broadband» деп сатады).

Бір-бірімен жапсарласқанның кемшіліктері

Жапырақтас әдістерді қолдану жалпы кешігуді арттырады. Өйткені пакеттерді декодтау үшін жапырақтас блок толығымен қабылдалуы тиіс. Сондай-ақ, жапырақтатандар қателердің құрылымын жасырады; жапырақтатандар болмаса, күрделі декодтау алгоритмдері қате құрылымын пайдаланып, жапырақтатамен жұптастырылған қарапайым декодерге қарағанда сенімді байланысқа қол жеткізе алады. Мұндай алгоритмнің мысалы – нейрондық желі құрылымдарына негізделген алгоритмдер.

Қателерді түзейтін кодтар үшін бағдарламалық қамтамасыз ету

Қателерді түзейтін кодтардың (ECC) мінез-құлқын бағдарламалық жасақтамада модельдеу, ECC-терді жобалау, тексеру және жақсарту үшін кең таралған тәжірибе. Алдағы 5G бесжелілік стандарты бағдарламалық ECC-лер үшін жаңа қолданыс салаларын ашады: бағдарламалық түрде анықталатын радио (SDR) контекстіндегі бұлтты радио қолжетімділік желілері (C-RAN). Мақсаты – ECC-лерді байланыс жүйесінде тікелей пайдалану. Мысалы, 5G-де бағдарламалық ECC-лер бұлтта орналасуы мүмкін, ал антенналар осы есептеу ресурстарына қосылады, бұл байланыс желісінің икемділігін арттырып, жүйенің энергия тиімділігін жоғарылатуға мүмкіндік береді. Осыған байланысты, төменде (толық емес) ашық кодты бағдарламалық жасақтамалардың тізімі келтірілген. AFF3CT (Жылдам алға түзету құралдары): C++ тіліндегі толық байланыс тізбегі (Turbo, LDPC, Polar кодтары және т.б. сияқты көптеген кодтарды қолдайды), өте жылдам және арналық кодтауға маманданған (симуляциялар үшін бағдарлама ретінде немесе SDR кітапханасы ретінде пайдалануға болады). IT++: сызықтық алгебра, сандық оптимизация, сигналды өңдеу, байланыс және статистика үшін C++ кластары мен функцияларының кітапханасы. OpenAir: 3GPP спецификацияларының (C тілінде) іске асырылуы, эволюцияланған пакеттік ядролық желілерге қатысты.