Кіріспе
Сымсыз байланыста қолданылатын қателерді түзету кодтары
Рид-Мюллер кодтары – сымсыз байланыс саласында, әсіресе терең ғарыш байланысында қолданылатын қателерді түзету кодтары. Сонымен қатар, ұсынылып отырған 5G стандарты басқару арнасындағы қателерді түзету үшін тығыз байланысты полярлық кодтарға сүйенеді. Теориялық және математикалық қасиеттерінің артықшылықтарына байланысты Рид-Мюллер кодтары теориялық информатикада кеңінен зерттелді. Рид-Мюллер кодтары Рид-Соломон кодтары мен Уолш-Хадамард кодын жалпылайды. Рид-Мюллер кодтары – жергілікті түрде тексерілетін, жергілікті түрде декодталатын және тізімдік декодтауға болатын сызықтық блок кодтары. Бұл қасиеттері оларды ықтималдықпен тексерілетін дәлелдемелерді жобалауда ерекше пайдалы етеді. Традициялық Рид-Мюллер кодтары екілік кодтар болып табылады, яғни хабарламалар мен кодтық сөздер екілік тізбектерден тұрады. Егер r және m 0 ≤ r ≤ m шартын қанағаттандыратын бүтін сандар болса, онда r және m параметрлері бар Рид-Мюллер коды RM(r, m) деп белгіленеді. k биттен тұратын хабарламаны кодтау қажет болғанда, аталған шарт орындалса, RM(r, m) коды 2m биттен тұратын кодтық сөзді шығарады. Рид-Мюллер кодтары 1954 жылы осы кодтарды ашқан Дэвид Э. Мюллер және алғашқы тиімді декодтау алгоритмін ұсынған Ирвинг С. Ридтің құрметіне аталған.
Төмен дәрежелі көптіктер арқылы сипаттау
Рид-Мюллер кодтары бірнеше түрлі (бірақ түпкілікті нәтижесінде эквивалентті) тәсілдермен сипатталуы мүмкін. Төмен дәрежелі полиномдарға негізделген сипаттама өте әдемі және оларды жергілікті түрде тексерілетін кодтар мен жергілікті түрде шешілетін кодтар ретінде қолдануға ерекше қолайлы.
Кодтаушы
Блок код бір немесе бірнеше кодтау функциясына ие болуы мүмкін, олар хабарламаларды кодтық сөздерге бейімдейді. Рид-Мюллер коды RM(r, m) хабарлама ұзындығына және блок ұзындығына ие. Бұл код үшін кодтауды анықтаудың бір жолы – m айнымалы және жалпы дәрежесі r болатын көп сызықты полиномиалдарды есептеуге негізделген. Екі элементі бар шекті өрістегі кез келген көп сызықты полиномиалды былай жазуға болады:
– полиномиалдың айнымалылары, ал – полиномиалдың коэффициенттері. Коэффициенттердің саны дәл болғандықтан, хабарлама осы коэффициенттер ретінде қолданылатын мәндерден тұрады. Осылайша, әрбір хабарлама m айнымалыдағы бірегей полиномиалды анықтайды. Кодтық сөзді құру үшін кодтаушы барлық есептеу нүктелерінде есептейді, онда ол қосындыны екілік қосылыс ретінде қарастырып, бит алады. Яғни, кодтау функциясы келесі арқылы анықталады:
Кодтық сөз бірегей түрде қалпына келтіру үшін жеткілікті екендігі Лагранж интерполяциясынан туындайды, ол полиномиалдың коэффициенттері жеткілікті есептеу нүктелері берілген кезде бірегей анықталады деп мәлімдейді. және барлық хабарламалар үшін орындалғандықтан, функция сызықтық түрлендіру болып табылады. Осылайша, Рид-Мюллер коды – сызықтық код.
Кіші дәрежелі көптік арқылы үлкен әліпбиге жалпылау
Шектелген өлшемді өрісте кіші дәрежелі полиномиалдарды қолдану арқылы Рид-Мюллер кодтарының анықтамасын өлшемі бар алфавиттерге кеңейтуге болады. Осы ретте , және оң бүтін сандар болсын, мұнда -ден үлкен деп есептелуі керек. кеңдігі бар хабарды кодтау үшін, хабар қайтадан айнымалы полиномиал ретінде қарастырылады, оның толық дәрежесі ең көп -ке тең және коэффициенттері -ден алынған. Мұндай полиномиалдың коэффициенті болады. -ның Рид-Мюллер кодтамасы – бұл барлық нүктелердегі оның барлық мәндерінің тізімі. Сондықтан блок ұзындығы -қа тең.
Генератор матрицасы
Reed-Muller RM(r, m) коды, r реті және N = 2m ұзындығымен, v0 және 1 ≤ i ≤ m аралығындағы vi-дің r-ге дейінгі клиндік көбейтінділері арқылы құрылған код. (Мұнда конвенция бойынша бір вектордан аз клиндік көбейтінді операцияның бірлік элементі болып табылады). Басқаша айтқанда, RM(r, m) коды үшін генератор матрицасын құруға болады, онда генератор матрицасының қатарлары ретінде 1 ≤ ik ≤ m шарты орындалатын r уақытқа дейінгі векторлар мен олардың клиндік көбейтінділерінің орналасулары қолданылады.
Рекурсивті құрылымды пайдалану арқылы сипаттау
Кез келген бүтін сандар үшін Reed-Muller коды RM(r,m) бар, ал RM(m,m) ғалам коды ретінде анықталады. RM(-1,m) тривиальды код ретінде анықталады. Қалған RM кодтары осы элементарлық кодтардан ұзындықты екі еселеу құрылымын пайдалана отырып құрастырылуы мүмкін.
Осы құрылыс бойынша RM(r,m) – ұзындығы n = 2^m, өлшемі k және ең аз қашықтығы d болатын екілік сызықтық блок коды (n, k, d). RM(r,m) кодының қос коды RM(m-r+1,m) болады. Бұл қайталау және SPC кодтарының дуалды екенін, биортогоналды және кеңейтілген Хамминг кодтарының да дуалды екенін, ал 1=k=n/2 кодтарының өзіне дуалды екенін көрсетеді.
RM ((r,m) r≤1 немесе r≥m-1 кодтарының қасиеттері
1=RM(0, m) кодтары – ұзындығы 1=N = 2^(m) қайталау кодтары, жылдамдығы және ең аз қашықтығы 1=RM(1, m) кодтары – ұзындығы 1=N = 2^(m) тексеру кодтары, жылдамдығы және ең аз қашықтығы 1=RM(m − 1, m) кодтары – ұзындығы 1=N = 2^(m) бір тексеру коді, жылдамдығы және ең аз қашықтығы 1=RM(m − 2, m) кодтары – ұзындығы 1=N = 2^(m) және ең аз қашықтығы бар кеңейтілген Хамминг кодтарының отбасы.