Төмен тығыздық теңсіздік тексеру кодтары: Ақпараттық теориядағы қателерді түзету әдісі
Low-density parity-check code
Төмен тығыздық теңсіздік тексеру кодтары (LDPC) – қателерді түзету коды. Бұл шулы каналдар арқылы мәліметтерді жеткізу үшін қолданылады, теориялық лимит жақын нәтижелер береді.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Сызықтық қателерді түзету коды
Linear error correcting code
Ақпарат теориясында, төмен тығыздықты тепе-теңдік тексеру (LDPC) коды – шулы тарату арнасы арқылы хабарды беру әдісі болып табылатын сызықтық қателерді түзету коды. LDPC коды сирек Таннер графигін (бипартитті графиктің кіші класы) пайдаланып құрастырылады. LDPC кодтары сыйымдылыққа жақындау кодтары болып табылады, яғни шу шегін симметриялық жадсыз арна үшін теориялық максимумға (Шеннон шегі) өте жақын орнатуға мүмкіндік беретін практикалық құрылымдар бар. Шу шегі – арна шуының жоғарғы шегін анықтайды, оған дейін жоғалған ақпараттың ықтималдығын қалағандай кішіге дейін азайтуға болады. Итеративті сенім тарату әдістерін қолдану арқылы LDPC кодтарын олардың блок ұзындығына пропорционал уақытта декодтауға болады. LDPC кодтары Роберт Г. Галлагердің құрметіне Галлагер кодтары деп те аталады, ол 1960 жылы Массачусетс технология институтында докторлық диссертациясында LDPC тұжырымдамасын жасаған. Алайда, LDPC кодтары есептеу ресурстарын көп қажет ететін итеративті декодтауды талап етеді, сондықтан ондаған жылдар бойы қолданылмады. 1993 жылы жаңадан ойлап табылған турбо кодтар, сол кезде қолданылған басқа кодтардан әлдеқайда жоғары өнімділік көрсететін итеративті декодтау кодтары екенін көрсетті, бірақ турбо кодтары патенттелген және пайдалану үшін төлем талап етілді. Бұл LDPC кодтарына деген жаңа қызығушылықты тудырды, олардың ұқсас өнімділік көрсетуі, бірақ әлдеқайда ескі және патентсіз екені дәлелденді. Қазір турбо кодтарына негізгі патенттің мерзімі аяқталған (2013 жылдың 29 тамызында), LDPC кодтары әлі де өздерінің техникалық артықшылықтары үшін қолданылады. LDPC кодтарының идеалды комбинаторлық қасиеттері бар екені көрсетілді. Галлагер өз диссертациясында LDPC кодтары бинарлы өрістердегі сызықтық кодтар үшін Гилберт-Варшамов шегін жоғары ықтималдылықпен орындайтынын көрсетті. 2020 жылы Галлагердің LDPC кодтары тізімдік декодтау сыйымдылығына жете алатыны және жалпы өрістердегі сызықтық кодтар үшін Гилберт-Варшамов шегіне де жете алатыны көрсетілді.
In information theory, a low density parity check (LDPC) code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel. An LDPC code is constructed using a sparse Tanner graph (subclass of the bipartite graph). LDPC codes are capacity approaching codes, which means that practical constructions exist that allow the noise threshold to be set very close to the theoretical maximum (the Shannon limit) for a symmetric memoryless channel. The noise threshold defines an upper bound for the channel noise, up to which the probability of lost information can be made as small as desired. Using iterative belief propagation techniques, LDPC codes can be decoded in time linear in their block length. LDPC codes are also known as Gallager codes, in honor of Robert G. Gallager, who developed the LDPC concept in his doctoral dissertation at the Massachusetts Institute of Technology in 1960. However, LDPC codes require computationally expensive iterative decoding, so they went unused for decades. In 1993 the newly invented turbo codes demonstrated that codes with iterative decoding could far outperform other codes used at that time, but turbo codes were patented and required a fee for use. This raised renewed interest in LDPC codes, which were shown to have similar performance, but were much older and patent free. Now that the fundamental patent for turbo codes has expired (on August 29, 2013), LDPC codes are still used for their technical merits. LDPC codes have been shown to have ideal combinatorial properties. In his dissertation, Gallager showed that LDPC codes achieve the Gilbert–Varshamov bound for linear codes over binary fields with high probability. In 2020 it was shown that Gallager's LDPC codes achieve list decoding capacity and also achieve the Gilbert–Varshamov bound for linear codes over general fields.
Тарих
1963 жылы Галлагер алғаш әзірлеген кезде іске асыру қиын болған LDPC кодтары, оның еңбегі 1996 жылы қайта ашылғанға дейін ұмытылып кеткен. 1993 жылы ашылған, сыйымдылыққа жақымды кодтардың тағы бір түрі – турбо кодтар, 1990 жылдардың соңында Deep Space Network және спутниктік байланыс сияқты қолданыстарда қолданылатын басты кодтау схемасы болды. Содан кейін LDPC кодтары ұқсас өнімділікті ұсынатын, патенттік төлемсіз балама ретінде қайтадан қызығушылық тудырды.
Impractical to implement when first developed by Gallager in 1963, LDPC codes were forgotten until his work was rediscovered in 1996. Turbo codes, another class of capacity approaching codes discovered in 1993, became the coding scheme of choice in the late 1990s, used for applications such as the Deep Space Network and satellite communications. LDPC codes then received renewed interest as a patent free alternative of similar performance.
Тораптық ақпаратты жаңарту
Соңғы жылдары, өзгермелі түйіндер мен шектеу түйіндерін жаңарту үшін баламалы кестелердің әсерін зерттеуге көп еңбек жұмсалды. LDPC кодтарын декодтау үшін қолданылған бастапқы техника «су басу» деп аталды. Бұл жаңарту түрі өзгермелі түйіннің мәнін жаңартпастан бұрын барлық шектеу түйіндерін жаңартуды және керісінше талап етті. Vila Casado және авторлар тобының кейінгі жұмыстарында, өзгермелі түйіндер ең жаңа қолжетімді тексеру түйіні ақпаратымен жаңартылатын баламалы жаңарту техникалары зерттелді. Бұл алгоритмдердің түйсігі – өз мәндері ең көп өзгеретін өзгермелі түйіндерді бірінші кезекте жаңарту қажет. Логарифмдік ықтималдық қатынасының (LLR) шамасы үлкен және бір жаңартудан екіншісіне айтарлықтай өзгермейтін жоғары сенімді түйіндер, басқа түйіндер сияқты белгісі мен шамасы кеңінен ауытқуы бар түйіндерге қарағанда, сирек жаңартуды қажет етеді. Бұл жоспарлау алгоритмдері су басуды қолданатын алгоритмдерге қарағанда конвергенция жылдамдығын арттырады және қателік деңгейін төмендетеді. Бұл төменгі қателік деңгейлері Ақпаратталған Динамикалық Жоспарлаудың (IDS) мүмкіндігі арқасында қол жеткізіледі.
In recent years, there has also been a great deal of work spent studying the effects of alternative schedules for variable node and constraint node update. The original technique that was used for decoding LDPC codes was known as flooding. This type of update required that, before updating a variable node, all constraint nodes needed to be updated and vice versa. In later work by Vila Casado et al., alternative update techniques were studied, in which variable nodes are updated with the newest available check node information. The intuition behind these algorithms is that variable nodes whose values vary the most are the ones that need to be updated first. Highly reliable nodes, whose log likelihood ratio (LLR) magnitude is large and does not change significantly from one update to the next, do not require updates with the same frequency as other nodes, whose sign and magnitude fluctuate more widely. These scheduling algorithms show greater speed of convergence and lower error floors than those that use flooding. These lower error floors are achieved by the ability of the Informed Dynamic Scheduling (IDS)
Су басуды қолданбайтын жоспарлау алгоритмдері қолданылғанда, итерацияның баламалы анықтамасы қолданылады. (n, k) LDPC коды үшін, жылдамдығы k/n болса, n өзгермелі және n – k шектеу түйіні жаңартылғанда толық итерация орын алады, олардың жаңарту ретіне қарамастан.
When nonflooding scheduling algorithms are used, an alternative definition of iteration is used. For an (n, k) LDPC code of rate k/n, a full iteration occurs when n variable and n − k constraint nodes have been updated, no matter the order in which they were updated.
Турбо кодтармен салыстырғанда
LDPC кодтарын басқа қуатты кодтау схемаларымен, мысалы, турбо кодтарымен салыстыруға болады. Бір жағынан, турбо кодтарының BER көрсеткіші төмен кодтардың шектеулеріне байланысты. LDPC кодтарында ең төменгі қашықтық шектеуі жоқ, бұл LDPC кодтары салыстырмалы түрде жоғары кодтау жылдамдықтарында (мысалы, 3/4, 5/6, 7/8) турбо кодтарынан тиімдірек болуы мүмкін дегенді білдіреді. Дегенмен, LDPC кодтары толықтай алмастыру емес: турбо кодтары төмен кодтау жылдамдықтарында (мысалы, 1/6, 1/3, 1/2) ең жақсы шешім болып табылады.
LDPC codes can be compared with other powerful coding schemes, e. g. turbo codes. In one hand, BER performance of turbo codes is influenced by low codes limitations. LDPC codes have no limitations of minimum distance, that indirectly means that LDPC codes may be more efficient on relatively large code rates (e. g. 3/4, 5/6, 7/8) than turbo codes. However, LDPC codes are not the complete replacement: turbo codes are the best solution at the lower code rates (e. g. 1/6, 1/3, 1/2).