Қателерді түзететін кодтар: Рид-Соломон кодтары

Reed-Solomon кодтары: қателерді түзететін кодтар, деректерді қорғау, CD, DVD, QR кодтарында қолданылады. Деректерді жеткізуде өте тиімді!

10 мин оқу

100%

Дереккөз: Reed–Solomon error correction — Wikipedia

Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.

Мазмұны

Кіріспе

Қателерді түзету кодтары

Рид-Соломон кодтары – 1960 жылы Ирвинг С. Рид және Густав Соломон ұсынған қателерді түзету кодтарының бір тобы. Олардың қолданылуы өте кең, оның ішінде MiniDiscs, CD, DVD, Blu-ray дискілері, QR кодтары, Data Matrix сияқты тұтынушылық технологиялар, DSL және WiMAX сияқты деректерді тарату технологиялары, спутниктік байланыс, DVB және ATSC сияқты хабар тарату жүйелері, сондай-ақ RAID 6 сияқты сақтау жүйелері бар. Рид-Соломон кодтары символдар деп аталатын шекті өріс элементтері жиынтығы ретінде қарастырылатын деректер блогымен жұмыс істейді. Рид-Соломон кодтары бірнеше символ қатесін анықтап, түзетуге қабілетті. t = n – k тексеру символдарымен деректерді толықтыру арқылы Рид-Соломон коды t-ға дейінгі кез келген қате символдарының комбинациясын анықтай алады (бірақ түзетпейді), немесе белгісіз орындарда t/2-ге дейінгі қате символдарының орнын тауып, түзетуге болады. Жою коды ретінде, ол алгоритмге белгілі және берілген орындарда t-ға дейінгі жоюларды түзетуге немесе қателер мен жоюлардың комбинацияларын анықтап, түзетуге мүмкіндік береді. Рид-Соломон кодтары бірнеше үзіліс біт қателерін түзету кодтары ретінде де қолайлы, себебі b + 1 тізбекті біт қатесі b өлшеміне дейінгі ең көп дегенде екі символға әсер ете алады. t-ны кодты жобалаушы таңдайды және оны кең шекте таңдауға болады. Рид-Соломон кодтарының екі негізгі түрі бар: бастапқы көрініс және BCH көрінісі. BCH көрінісі ең көп таралған, себебі BCH көрінісінің декодерлері жылдамырақ жұмыс істейді және бастапқы көрініс декодерлеріне қарағанда аз жұмыс жадын қажет етеді.

Тарих

Рид-Соломон кодтары 1960 жылы Ирвинг С. Рид пен Густав Соломон әзірледі, олар сол кезде МТИ Линкольн зертханасының қызметкерлері болған. Олардың маңызды мақаласы "Кейбір шекті өрістердегі полиномдық кодтар" деп аталды. Рид пен Соломон мақаласында сипатталған бастапқы кодтау схемасы кодталатын хабарламаға негізделген өзгермелі полиномды пайдаланды, онда кодтаушы мен декодерге кодталатын мәндердің (бағалау нүктелерінің) белгілі бір жиынтығы ғана белгілі болды. Бастапқы теориялық декодер алынған хабарламаның n (кодталған хабарлама ұзындығы) мәндерінің ішіндегі k (кодталмаған хабарлама ұзындығы) мәндік жиынтығына негізделген мүмкін полиномдарды жасады, содан кейін ең көп кездесетін полиномды дұрыс деп таңдады, бірақ бұл барлық жағдайларда, тіпті ең қарапайым жағдайларда да тиімді болмады. Бұл мәселе бастапқыда схеманы кодтаушы мен декодерге белгілі тұрақты полиномға негізделген BCH кодына ұқсас схемаға өзгерту арқылы шешілді, бірақ кейіннен бастапқы схемаға негізделген практикалық декодерлер жасалды, бірақ олар BCH схемаларынан баяу болды. Соның салдарынан Рид-Соломон кодтарының екі негізгі түрі пайда болды: бастапқы кодтау схемасын қолданатын және BCH кодтау схемасын қолданатын. 1960 жылы Даниэль Горенштейн мен Нил Зиерлер BCH кодтары үшін практикалық тұрақты полиномдық декодерді жасады, ол 1960 жылдың қаңтар айында Зиерлердің МТИ Линкольн зертханасының есебінде және кейіннен 1961 жылдың маусым айында жарияланған мақалада сипатталды. Горенштейн-Зиерлер декодері және BCH кодтарына қатысты жұмыстар В. Уэсли Петерсонның "Қателерді түзету кодтары" (1961) кітабында сипатталған. 1963 жылы (немесе одан ертерек) Дж. Стоун (және басқалар) Рид-Соломон кодтарының BCH схемасын тұрақты генераторлық полиномды пайдалану арқылы қолдануға болатынын анықтады, бұл кодтарды BCH кодтарының ерекше класына айналдырды. Бірақ бастапқы кодтау схемасына негізделген Рид-Соломон кодтары BCH кодтарының класына жатпайды және бағалау нүктелерінің жиынтығына байланысты олар тіпті циклдік кодтар да емес. 1969 жылы Эльвин Берлекэмп пен Джеймс Мэйси жетілдірілген BCH схемасы декодерін жасады, ол Берлекэмп-Мэйси декодтау алгоритмі деп белгілі болды. 1975 жылы Ясуо Сугияма кеңейтілген Евклид алгоритміне негізделген тағы бір жетілдірілген BCH схемасы декодерін жасады. 1977 жылы Рид-Соломон кодтары "Вояджер" бағдарламасында біріктірілген қателерді түзету кодтары түрінде қолданылды. Бұқаралық өндірістегі тұтыну өнімдеріндегі алғашқы коммерциялық қолданыс 1982 жылы компакт-дискімен пайда болды, онда екі араластырылған Рид-Соломон коды қолданылды. Бүгінде Рид-Соломон кодтары цифрлық сақтау құрылғыларында және цифрлық байланыс стандарттарында кеңінен қолданылады, бірақ олар баяу Бозе-Чоудхури-Хоккенгем (BCH) кодтарымен ауыстырылуда. Мысалы, Reed-Solomon кодтары Digital Video Broadcasting (DVB) стандартында DVB S-пен бірге конволюциялық ішкі кодпен қолданылады, бірақ BCH кодтары LDPC-мен оның DVB S2 жалғастырғышында қолданылады. 1986 жылы Berlekamp-Welch алгоритмі деп аталатын бастапқы схемалық декодер жасалды. 1996 жылы Мадху Судан және басқалар бастапқы схемалық декодерлердің тізімдік декодерлер немесе жұмсақ декодерлер деп аталатын түрлерін жасады, ал осы типтегі декодерлер бойынша жұмыс жалғасуда (мысалы, Guruswami-Sudan тізімдік декодтау алгоритмі). 2002 жылы Shuhong Gao кеңейтілген Евклид алгоритміне негізделген тағы бір бастапқы схемалық декодерді жасады.

Reed–Solomon codes were developed in 1960 by Irving S. Reed and Gustave Solomon, who were then staff members of MIT Lincoln Laboratory. Their seminal article was titled "Polynomial Codes over Certain Finite Fields". The original encoding scheme described in the Reed & Solomon article used a variable polynomial based on the message to be encoded where only a fixed set of values (evaluation points) to be encoded are known to encoder and decoder. The original theoretical decoder generated potential polynomials based on subsets of k (unencoded message length) out of n (encoded message length) values of a received message, choosing the most popular polynomial as the correct one, which was impractical for all but the simplest of cases. This was initially resolved by changing the original scheme to a BCH code like scheme based on a fixed polynomial known to both encoder and decoder, but later, practical decoders based on the original scheme were developed, although slower than the BCH schemes. The result of this is that there are two main types of Reed Solomon codes, ones that use the original encoding scheme, and ones that use the BCH encoding scheme. Also in 1960, a practical fixed polynomial decoder for BCH codes developed by Daniel Gorenstein and Neal Zierler was described in an MIT Lincoln Laboratory report by Zierler in January 1960 and later in a paper in June 1961. The Gorenstein–Zierler decoder and the related work on BCH codes are described in a book Error Correcting Codes by W. Wesley Peterson (1961). By 1963 (or possibly earlier), J. J. Stone (and others) recognized that Reed Solomon codes could use the BCH scheme of using a fixed generator polynomial, making such codes a special class of BCH codes, but Reed Solomon codes based on the original encoding scheme, are not a class of BCH codes, and depending on the set of evaluation points, they are not even cyclic codes. In 1969, an improved BCH scheme decoder was developed by Elwyn Berlekamp and James Massey, and has since been known as the Berlekamp–Massey decoding algorithm. In 1975, another improved BCH scheme decoder was developed by Yasuo Sugiyama, based on the extended Euclidean algorithm. In 1977, Reed–Solomon codes were implemented in the Voyager program in the form of concatenated error correction codes. The first commercial application in mass produced consumer products appeared in 1982 with the compact disc, where two interleaved Reed–Solomon codes are used. Today, Reed–Solomon codes are widely implemented in digital storage devices and digital communication standards, though they are being slowly replaced by Bose–Chaudhuri–Hocquenghem (BCH) codes. For example, Reed–Solomon codes are used in the Digital Video Broadcasting (DVB) standard DVB S, in conjunction with a convolutional inner code, but BCH codes are used with LDPC in its successor, DVB S2. In 1986, an original scheme decoder known as the Berlekamp–Welch algorithm was developed. In 1996, variations of original scheme decoders called list decoders or soft decoders were developed by Madhu Sudan and others, and work continues on these types of decoders – see Guruswami–Sudan list decoding algorithm. In 2002, another original scheme decoder was developed by Shuhong Gao, based on the extended Euclidean algorithm.

Штрих-код

PDF 417, MaxiCode, Datamatrix, QR Code және Aztec Code сияқты екі өлшемді штрих-кодтардың көбі Reed–Solomon қатесін түзетуді пайдаланады, штрих-кодтың бір бөлігі зақымдалған жағдайда да дұрыс оқуға мүмкіндік береді. Штрих-кодты сканері штрих-код символын тани алмаса, оны жойылған символ ретінде қарастырады. Reed–Solomon кодтамасы бір өлшемді штрих-кодтарда сирек кездеседі, бірақ PostBar символогиясында қолданылады.

Деректерді беру

Reed-Solomon кодтарының арнайы түрлері, атап айтқанда Cauchy RS және Vandermonde RS, деректерді жою арнасы арқылы берудің сенімсіздігін жеңу үшін қолданылуы мүмкін. Кодтау процесі RS(N, K) кодын пайдаланады, нәтижесінде әрқайсысы K символ дерек сақтайтын N символ ұзындығындағы N кодтық сөз жаратылады, содан кейін олар жою арнасы арқылы жіберіледі. Екінші жақтан алынған K кодтық сөздің кез келген комбинациясы барлық N кодтық сөзді қалпына келтіруге жеткілікті. Кодтың жылдамдығы әдетте 1/2-ге тең, егер арнаның жою ықтималдығы дұрыс модельденіп, одан аз болмаса. Қорытындылай келе, N әдетте 2K-ға тең, яғни жіберілген барлық кодтық сөздерді қалпына келтіру үшін жіберілген кодтық сөздердің кем дегенде жартысы алынуы керек. Reed-Solomon кодтары xDSL жүйелерінде және CCSDS ғарыш байланысы протоколының сипаттамаларында алдын ала қателерді түзету түрі ретінде де қолданылады.

Ескертпелер

Дизайнерлер Reed–Solomon код блоктарының "табиғи" өлшемдерін пайдалануға міндетті емес. "Қысқарту" деп аталатын әдіс үлкен кодтан кез келген қажетті өлшемдегі кіші кодты жасауға мүмкіндік береді. Мысалы, кеңінен қолданылатын (255,223) кодын (160,128) кодына түрлендіру үшін бастапқы блоктың пайдаланылмаған бөлігі 95 екілік нөлмен толтырылып, олар жіберілмейді. Декодерде блоктың сол бөлігі бинарлық нөлдермен толтырылады. Делсарте–Гёталс–Сейдель теоремасы қысқартылған Reed–Solomon кодтарының қолданылуына мысал келтіреді. Қысқартумен қатар, "пункциялау" деп аталатын әдіс кодталған теңдік белгілерінің кейбіреулерін жоюға мүмкіндік береді.

BCH көрініс декодерлері

Осы бөлімде сипатталған декодерлер коды сөзді коэффициенттер тізбегі ретінде қарастырады, осыған BCH көзқарасын қолданады. Олар кодтаушы мен декодерге белгілі бір тұрақты генераторлық полиномды пайдаланады.

Питерсон-Горенштейн-Циерлер декодері

Даниэль Горенштейн мен Нил Зиерлер 1960 жылдың қаңтарында MIT Линкольн зертханасының Зиерлер есебінде сипатталған, ал кейіннен 1961 жылдың маусым айында жарияланған мақалада толыққанды декодерді жасады. Горенштейн–Зиерлер декодері және BCH кодтарына қатысты жұмыстар В. Уэсли Петерсонның "Қателерді түзету кодтары" кітабында (1961) сипатталған.

Синдромды кодтау

Декодер алынған көпмүшені We нүктелерінде есептеуден бастайды. Осы есептеулердің нәтижелерін "синдромдар" деп атаймыз, Sj. Олар былай анықталады:

Ескеріңіз, өйткені көпмүшенің We нүктелерінде түбірлері бар, бұл бұрынғы бөлімде көрсетілгендей. Синдромдарды қарастырудың артықшылығы – хабар көпмүшесі есептен шығарылады. Яғни, синдромдар тек қатеге байланысты және жіберілетін хабардың мазмұнына әсер етпейді. Егер барлық синдромдар нөлге тең болса, алгоритм осы жерде тоқтап, хабарламаның жолда бұзылмағанын хабарлайды.

Қате табушы полиномының түбірін табыңыз

Қате орналасу полиномиалын құру үшін соңғы қадамда табылған Λi коэффициенттерін пайдаланыңыз. Қателік орналасу полиномының түбірлерін толық іздеу арқылы табуға болады. Xk қателік локаторлары осы түбірлердің кері шамалары болып табылады. Қате орналасу полиномының коэффициенттерінің ретін кері ауыстыруға болады, онда кері полиномның түбірлері қателік локаторлары болады (кері шамалары емес). Чьен іздеуі – бұл қадамды тиімді іске асырудың бір жолы.

Қате мәндерін есептеу

Xk қателердің орналасқан жерлері белгілі болғаннан кейін, қателердің шамаларын анықтауға болады. Бұл жоғарыда келтірілген қате теңдеулер матрицасында Yk-ны тікелей есептеу арқылы немесе Форни алгоритмін пайдалану арқылы жасалуы мүмкін.

Қателер орналасуын есептеу

Xk-нің логарифмін есептеп, ik-ні табыңыз. Мұндай есептеулер көбінесе алдын ала дайындалған кестелерді пайдаланып жасалады.

Қателерді түзету

Соңында, e(x) ik және eik негізінде жасалады, содан кейін r(x) -тен алынып, қателер түзетілген бастапқы жіберілген хабарлама s(x) қалпына келтіріледі.

Берлекамп Масси декодері

Берлекамп–Масси алгоритмі – қателік локатор полиномін табудың балама итерациялық әдісі. Әр итерация барысында, ол қателіктер саны е деп белгіленген болжаммен, Λ(x) ағымдағы мәніне сүйене отырып, айырмашылықты есептейді:

және содан кейін Δ қайта есептелгенде нөлге тең болатындай етіп Λ(x) және e-ні реттейді. «Берлекамп–Масси алгоритмі» мақаласында процедураның толық сипаттамасы келтірілген. Келесі мысалда Λ(x) үшін C(x) белгісі қолданылады.

Дискретті Фурье трансформациясын пайдаланатын декодер

Декодтау үшін дискретті Фурье трансформациясын қолдануға болады. Синдром атауларымен қайшылықты болдырмау үшін, кодталған кодты c(x) = s(x) деп белгілейік. r(x) және e(x) жоғарыда көрсетілгендей. C(x), E(x) және R(x) c(x), e(x) және r(x) дискретті Фурье трансформациялары ретінде анықталады. r(x) = c(x) + e(x) болғандықтан және дискретті Фурье трансформациясы сызықтық оператор болғандықтан, R(x) = C(x) + E(x). Дискретті Фурье трансформациясын пайдаланып r(x)-ді R(x)-ке түрлендіріңіз. Дискретті Фурье трансформациясының есептеуі синдромдардың есептеуімен бірдей болғандықтан, R(x) және E(x) t коэффициенттері синдромдармен сәйкес келеді: синдромдар ретінде пайдаланыңыз (олар бірдей) және жоғарыда аталған декодерлердің кез келгенінің әдістерін қолданып, қателік локатор полиномын құрыңыз. v = қателер саны болсын. E(x)-ді белгілі коэффициенттерді , қателік локатор полиномын және осы формулаларды пайдаланып анықтаңыз. Содан кейін C(x) = R(x) − E(x) есептеліп, C(x)-тің кері трансформациясы (полиномдық интерполяция) алынып, c(x) шығарылады.

Қателерді түзетуден тыс кодтау

Синглтон шектеуі (Singleton bound) (n,k) өлшемді сызықтық блок кодтың ең аз қашықтығы d-ның n − k + 1-ден аспайтынын көрсетеді. d қашықтығы әдетте қателерді түзету мүмкіндігін ⌊(d−1) / 2⌋-мен шектейтін түсінік болды. Рид-Соломон коды осы шектеуге теңдікпен жетеді, демек (n−k) / 2 қателерге дейін түзетуге қабілетті. Дегенмен, бұл қателерді түзету шектеуі нақты емес. 1999 жылы MIT-де Мадху Судан мен Венкатесан Гурусвами "Рид-Соломон және алгебралық геометрия кодтарының жақсартылған кодтамасы" ("Improved Decoding of Reed–Solomon and Algebraic Geometry Codes") атты еңбегін жариялады, онда кодтың ең аз қашықтығының жартысынан астам қателерді түзетуге мүмкіндік беретін алгоритм ұсынылды. Бұл Рид-Соломон кодтарына және жалпы алғанда алгебралық геометриялық кодтарға қатысты. Бұл алгоритм кодтық сөздердің тізімін құрайды (бұл тізімдік кодтау алгоритмі) және интерполяцияға және полиномдарды көбейткіштерге жіктеуге негізделген, сондай-ақ оның кеңейтімдеріне. 2023 жылы үш маңызды зерттеуге сүйене отырып, кодтау теориясының мамандары Рид-Соломон кодтары, кездейсоқ бағалау нүктелерінде анықталғанда, жоғары ықтималдықпен сызықтық өлшемді әліпбилерде тізімдік кодтау сыйымдылығына (n−k қателерге дейін) жете алатынын көрсетті. Алайда, бұл нәтиже алгоритмдік емес, комбинаторлық сипатта болады.

Жұмсақ кодтау

Жоғарыда сипатталған алгебралық декодтау әдістері – бұл қатаң шешім әдістері, яғни әрбір символ үшін оның мәні туралы нақты шешім қабылданады. Мысалы, декодер әрбір символға арна демодуляторының осы символдың дұрыстығына сену деңгейіне сәйкес келетін қосымша мән тағайындауы мүмкін. Теориялық лимиттерге жақын қателерді түзету мүмкіндігін қамтамасыз ететін итеративті жұмсақ шешімді сенім тарату декодтау әдістерін пайдаланатын LDPC және турбо кодтарының пайда болуы, дәстүрлі алгебралық кодтарға жұмсақ шешімді декодтауды қолдануға қызығушылықты арттырды. 2003 жылы Ральф Кёттер және Александр Варди Рид-Соломон кодтары үшін полиномиалдық уақытта жұмсақ шешімді алгебралық тізімдік декодтау алгоритмін ұсынды, ол Судан мен Гурусвамидың еңбектеріне негізделген. 2016 жылы Стивен Дж. Франк және Джозеф Х. Тейлор жаңа жұмсақ шешімді декодерді жариялады.

Рид Соломонның түпнұсқалық көрініс декодерлері

Осы бөлімде сипатталған декодерлер кодталған сөзді Рид-Соломонның бастапқы тұжырымы бойынша, кодталатын хабарға негізделген полиномдық мәндер тізбегі ретінде қарастырады. Кодтаушы мен декодер бірдей белгілі бір мәндер жиынын пайдаланады, ал декодер алынған хабардан кодтау полиномын (және қажет болған жағдайда қателіктерді анықтау полиномын) қалпына келтіреді.

Теориялық декодер

ең танымал хабар полиномиалын тауып, қателерді түзететін теориялық декодер сипатталды. Декодер кодталған сөздің мәндер тізбесін жасау үшін қолданылған кодтау әдісін және мәндер жиынтығын ғана біледі. Бастапқы хабарлама, полином және кез келген қателер белгісіз. Декодтау процедурасы, қабылданған код сөзіндегі кез келген қателерді жоюға жеткілікті сәйкес полиномдар алынғанға дейін, бір мезгілде k-дан алынған n код сөздерінің әртүрлі кіші жиынтықтарында Лагранж интерполяциясы сияқты әдісті қолдануға болады. Полином анықталғаннан кейін, код сөзіндегі кез келген қателерді тиісті код сөздерінің мәндерін қайта есептеу арқылы түзетуге болады. Өкінішке орай, ең қарапайым жағдайлардан басқа барлық жағдайларда, кіші жиынтықтардың саны тым көп болғандықтан, алгоритм практикалық емес. Кіші жиынтықтардың саны – биномдық коэффициент, және тіпті қарапайым кодтар үшін де кіші жиынтықтардың саны қолдануға мүмкін емес. 3 қателіктерді түзете алатын код үшін, қарапайым теориялық декодер 359 миллиард кіші жиынтықты қарастыруға тура келеді.

Берлекамп Велш декодері

1986 жылы Берлекamp–Уэлч алгоритмі деп аталатын декодер әзірленді. Бұл декодер бастапқы хабарлама полиномиалын қалпына келтіре алады, сонымен қатар қателіктерге сәйкес келетін кіріс мәндері үшін нөлдерді беретін қателік "орналастырушы" полиномиалын да анықтайды. Бұл алгоритмнің уақыттық күрделігі , мұнда – хабарламадағы мәндер саны. Қалпына келтірілген полином бастапқы хабарды қалпына келтіру үшін (қажет болған жағдайда қайта есептеу үшін) қолданылады.

Гао декодері

2002 жылы Шухон Гао кеңейтілген Евклид алгоритмі негізінде жақсартылған декодерді жасады.