Рид-Мюллер коды - Reed–Muller code

Рид-Мюллер коды RM (r, m)
Есімімен аталдыИрвинг С.Рид және Дэвид Э. Мюллер
Жіктелуі
ТүріСызықтық блок коды
Блоктың ұзындығы
Хабар ұзындығы
Бағасы
Қашықтық
Алфавит мөлшері
Нота-код

Рид-Мюллер кодтары болып табылады қателерді түзететін кодтар сымсыз байланыс қосымшаларында, әсіресе ғарыштық байланыста қолданылады[1]. Сонымен қатар, ұсынылған 5G стандарты[2] бір-бірімен тығыз байланысты полярлық кодтар[3] басқару каналындағы қателерді түзету үшін. Өздерінің қолайлы теориялық және математикалық қасиеттерінің арқасында Рид-Мюллер кодтары да көп зерттелген теориялық информатика.

Рид-Мюллер кодтары Рид-Сүлеймен кодтары және Уолш – Хадамамар коды. Рид-Мюллер кодтары сызықтық блоктық кодтар бұл жергілікті деңгейде тексеруге болады, жергілікті декодтау, және декодталатын тізім. Бұл қасиеттер оларды әсіресе дизайнда пайдалы етеді ықтималдықпен тексерілетін дәлелдемелер.

Дәстүрлі Рид-Мюллер кодтары - бұл екілік кодтар, бұл хабарламалар мен кодтық сөздер екілік жолдар екенін білдіреді. Қашан р және м 0 ≤ бар бүтін сандар рм, параметрлері бар Рид-Мюллер коды р және м RM деп белгіленеді (рм). Тұратын хабарламаны кодтауды сұрағанда к бит, қайда ұстайды, RM (рм) код 2-ден тұратын кодтық сөз шығарадым биттер.

Рид-Мюллер кодтары аталған Дэвид Э. Мюллер, 1954 жылы кодтарды ашқан[4], және Ирвинг С.Рид, бірінші тиімді декодтау алгоритмін ұсынған[5].

Төмен дәрежелі полиномдарды қолдану арқылы сипаттама

Рид-Мюллер кодтарын бірнеше түрлі сипаттауға болады (бірақ, сайып келгенде). Төмен дәрежелі полиномдарға негізделген сипаттама өте талғампаз және оларды қолдануға сәйкес келеді жергілікті тексерілетін кодтар және жергілікті декодталатын кодтар.[6]

Кодтаушы

A блок коды бір немесе бірнеше кодтау функциялары болуы мүмкін хабарламаларды картаға түсіреді кодты сөздерге . Рид-Мюллер коды RM (р, м) бар хабарлама ұзақтығы және блок ұзындығы . Осы код үшін кодтауды анықтаудың бір әдісі бағалауға негізделген көп сызықты көпмүшелер бірге м айнымалылар және жалпы дәреже р. Әрбір көп сызықты көпмүшелік ақырлы өріс екі элементпен келесідей жазуға болады:

The көпмүшенің айнымалылары және мәндері көпмүшенің коэффициенттері болып табылады. Себебі дәл бар коэффициенттер, хабарлама тұрады осы коэффициенттер ретінде қолдануға болатын мәндер. Осылайша, әр хабарлама ерекше көпмүшені тудырады жылы м айнымалылар. Код сөзін құру , кодтаушы бағалайды барлық бағалау нүктелерінде , онда ол қосынды модульді екіге қосу үшін интерпретациялау үшін түсіндіреді . Яғни, кодтау функциясы арқылы анықталады

Codeword фактісі бірегей қалпына келтіруге жеткілікті келесіден Лагранж интерполяциясы, онда полиномның коэффициенттері жеткілікті көп бағалау нүктелері берілген кезде бірегей анықталады деп көрсетілген. Бастап және барлық хабарламаларға арналған , функциясы Бұл сызықтық карта. Сонымен Рид-Мюллер коды - а сызықтық код.

Мысал

Код үшін RM (2, 4), параметрлері келесідей:

Келіңіздер жаңа ғана анықталған кодтау функциясы болуы керек. X = 1 1010 010101 жолының ұзындығын 11 кодтау үшін, кодер алдымен көпмүшені құрастырады 4 айнымалы:

Содан кейін ол осы көпмүшені барлық 16 бағалау нүктесінде бағалайды:
Нәтижесінде C (1 1010 010101) = 1111 1010 0101 0000 орындалады.

Декодер

Жоғарыда айтылғандай, Lagrange интерполяциясын кодты сөзден хабарламаны тиімді алу үшін пайдалануға болады. Дегенмен, декодер жұмыс істеуі керек, тіпті егер кодты сөз бірнеше позицияда бүлінген болса, яғни алынған сөз кез-келген кодтан өзгеше болғанда. Бұл жағдайда декодтаудың жергілікті процедурасы көмектесе алады.

Төмен дәрежелі полиномдар арқылы үлкен алфавиттерге жалпылау

Төмен дәрежелі полиномдарды ақырлы өріске қолдану өлшемі , Рид-Мюллер кодтарының анықтамасын өлшемді алфавиттерге дейін кеңейтуге болады . Келіңіздер және натурал сандар болыңыз, мұндағы қарағанда үлкен деп ойлау керек . Хабарламаны кодтау үшін туралы , хабарлама қайтадан түсіндіріледі -өзгермелі көпмүшелік жалпы дәреже және бастап коэффициентімен . Мұндай көпмүшелік шынымен де бар коэффициенттер. Рид-Мюллердің кодталуы барлық бағалау тізімі болып табылады бәрінен бұрын . Осылайша блоктың ұзындығы .

Генератор матрицасын қолдану арқылы сипаттама

A генератор матрицасы Рид-Мюллер коды үшін RM (р, м) ұзындығы N = 2м келесідей құрылуы мүмкін. Барлығының жиынтығын жазайық м-өлшемді екілік векторлар:

Біз анықтаймыз N-өлшемдік кеңістік The индикатор векторлары

ішкі жиындарда автор:

бірге, сонымен бірге , екілік амал

деп аталады сына өнімі (деп шатастыруға болмайды сына өнімі сыртқы алгебрада анықталған). Мұнда, және болып табылады (N-өлшемді екілік векторлар), және амал өрістегі әдеттегі көбейту .

болып табылады м-өрістің үстіндегі векторлық кеңістік , сондықтан жазуға болады

Біз анықтаймыз N-өлшемдік кеңістік ұзындығы келесі векторлар және

Мұндағы 1 ≤ i ≤ м және Hмен болып табылады гиперпландар жылы (өлшеммен м − 1):

Генератор матрицасы

Рид-Мюллер RM (р, м) тапсырыс коды р және ұзындығы N = 2м дегеніміз - жасалған код v0 және дейін сыналардан жасалған бұйымдар р туралы vмен, 1 ≤ менм (мұнда шарт бойынша бір вектордан аз сына көбейтіндісі операцияға сәйкестендіру болып табылады). Басқаша айтқанда, үшін генератор матрицасын құра аламыз RM (р, м) дейін, векторларды және олардың сына өнімі бойынша ауыстыруларын қолдана отырып р бір уақытта , генератор матрицасының жолдары ретінде, қайда 1 ≤ менкм.

1-мысал

Келіңіздер м = 3. Сонда N = 8, және

және

RM (1,3) коды жиынтық арқылы жасалады

немесе одан да көп матрицаның жолдары бойынша:

2-мысал

RM (2,3) коды жиынтық бойынша жасалады:

немесе одан да көп матрицаның жолдары бойынша:

Қасиеттері

Келесі қасиеттер:

  1. Сынаға дейінгі барлық мүмкін бұйымдардың жиынтығы м туралы vмен үшін негіз құрайды .
  2. RM (р, м) код бар дәреже
  3. RM (р, м) = RM (р, м - 1) | RM (р − 1, м − 1) қайда '|' дегенді білдіреді бар өнім екі кодтың
  4. RM (р, м) минимумға ие Салмақ салмағы 2мр.

Дәлел

  1. Сонда

    осындай векторлар және өлшемі бар N сондықтан. екенін тексеру жеткілікті N векторлар аралығы; баламалы түрде мұны тексеру жеткілікті .

    Келіңіздер х ұзындықтың екілік векторы болу керек м, элементі X. Келіңіздер (х)мен белгілеу менмың элементі х. Анықтаңыз

    мұндағы 1 ≤ менм.

    Содан кейін

    Сына өнімнің дистрибутивтілігі арқылы кеңею береді . Содан кейін векторлардан бастап аралық Бізде бар .
  2. Авторы 1, барлық осындай сына бұйымдары сызықтық тәуелсіз болуы керек, сондықтан RM дәрежесі (р, м) жай векторлардың саны болуы керек.
  3. Келтірілмесе.
  4. Индукция бойынша.
    The RM (0,м) код - ұзындықтың қайталану коды N =2м және салмақ N = 2м−0 = 2мр. Авторы 1 және салмағы 1 = 20 = 2мр.
    Мақала штрих-өнім (кодтау теориясы) екі кодтан тұратын штрих-көбейтіндісінің салмағы туралы дәлел келтіреді C1 , C2 арқылы беріледі
    Егер 0 < р < м және егер
    1. RM (р,м − 1) салмағы бар 2м−1−р
    2. RM (р − 1,м − 1) салмағы бар 2м−1−(р−1) = 2мр
    онда штанганың салмағы бар

RM кодтарын декодтау

RM (р, м) кодтарының көмегімен декодтауға болады логикалық декодтау. Көпшіліктің логикалық декодтауының негізгі идеясы әрбір алынған код сөзінің элементі үшін бірнеше бақылау сомасын құру болып табылады. Әр түрлі бақылау сомаларының әрқайсысы бірдей мәнге ие болуы керек болғандықтан (мысалы, хабарлама сөзінің салмағының мәні), біз хабарлама сөзінің мәнін ашу үшін логикалық декодтауды қолдана аламыз. Көпмүшенің әрбір реті декодталғаннан кейін, алынған сөз сәйкесінше кодталған сөздерді алып тастау арқылы өзгертіледі, осы уақытқа дейін хабарлама үлестері бойынша салмақталған. рRM кодының реті, біз соңғы қабылданған код сөзіне келгенге дейін r + 1 ретеративті түрде декодтауымыз керек. Сондай-ақ, хабарлама биттерінің мәндері осы схема арқылы есептеледі; ақыр соңында біз код сөзін генератор матрицасымен хабарлама сөзін (жай ғана декодталған) көбейту арқылы есептей аламыз.

Егер декодтау сәтті болса, бір нәтиже - нөлдік модификацияланған алынған сөз болуы керек, соңында (р + 1) көпшіліктің логикалық дешифрлеуі арқылы кезеңдік декодтау. Бұл техниканы Ирвинг С.Рид ұсынған, ал басқа шектеулі геометриялық кодтарға қолданған кезде жалпы болып табылады.

Рекурсивті құрылысты қолдану арқылы сипаттама

Рид-Мюллер коды RM (р, м) кез келген бүтін сандар үшін бар және . RM (м, м) ғалам ретінде анықталады () код. RM (−1, m) тривиальды код ретінде анықталады (). Қалған RM кодтары осы қарапайым кодтардан ұзындықты екі еселенетін конструкцияны қолдану арқылы жасалуы мүмкін

Осы құрылыстан RM (р, м) екілік болып табылады сызықтық блок коды (n, к, г.) ұзындығымен n = 2м, өлшем және минималды арақашықтық үшін . The қос код RM дейін (р, м) RM (м-р-1,м). Бұл қайталану және SPC кодтарының қосарланғандығын, биортогональды және кеңейтілген Хамминг кодтарының қосарланғандығын және кодтары бар кодтар екенін көрсетеді к = n/2 екі жақты.

Рид-Мюллер кодтарының ерекше жағдайлары

M≤5 үшін барлық RM (r, m) кодтарының кестесі

Барлық RM (рм) кодтары бар және алфавиттің өлшемі 2 [n, k, d] стандартымен түсіндірілген мұнда көрсетілген кодтау теориясының белгісі үшін блок кодтары. Код RM (рм) Бұл -код, яғни ол сызықтық код астам екілік алфавит, бар блок ұзындығы , хабарлама ұзақтығы (немесе өлшем) к, және минималды арақашықтық .

RM (м, м)
(2м, 2м, 1)
ғалам кодтары
RM (5,5)
(32,32,1)
RM (4,4)
(16,16,1)
RM (м − 1, м)
(2м, 2м−1, 2)
ХҚК кодтар
RM (3,3)
(8,8,1)
RM (4,5)
(32,31,2)
RM (2,2)
(4,4,1)
RM (3,4)
(16,15,2)
RM (м − 2, м)
(2м, 2мм−1, 4)
ішкі. Hamming кодтары
RM (1,1)
(2,2,1)
RM (2,3)
(8,7,2)
RM (3,5)
(32,26,4)
RM (0,0)
(1,1,1)
RM (1,2)
(4,3,2)
RM (2,4)
(16,11,4)
RM (0,1)
(2,1,2)
RM (1,3)
(8,4,4)
RM (2,5)
(32,16,8)
өзіндік қос кодтар
RM (−1,0)
(1,0,)
RM (0,2)
(4,1,4)
RM (1,4)
(16,5,8)
RM (-1,1)
(2,0,)
RM (0,3)
(8,1,8)
RM (1,5)
(32,6,16)
RM (−1,2)
(4,0,)
RM (0,4)
(16,1,16)
RM (1,м)
(2м, м+1, 2м−1)
Тесілген Хадамар кодтары
RM (−1,3)
(8,0,)
RM (0,5)
(32,1,32)
RM (−1,4)
(16,0,)
RM (0,м)
(2м, 1, 2м)
қайталау кодтары
RM (−1,5)
(32,0,)
RM (−1,м)
(2м, 0, ∞)
тривиальды кодтар

R≤1 немесе r≥m-1 үшін RM (r, m) кодтарының қасиеттері

  • RM (0,м) кодтары болып табылады қайталау кодтары ұзындығы N = 2м, ставка және минималды арақашықтық .
  • RM (1,м) кодтары болып табылады паритетті тексеру кодтары ұзындығы N = 2м, ставка және минималды арақашықтық .
  • RM (м − 1, м) кодтары болып табылады бір паритетті тексеру кодтары ұзындығы N = 2м, ставка және минималды арақашықтық .

Әдебиеттер тізімі

  1. ^ Мэсси, Джеймс Л. (1992), «Терең ғарыштық байланыс және кодтау: көкте жасалған неке», Спутниктік және терең ғарыштық байланыстың жетілдірілген әдістері, Бақылау және ақпарат ғылымдарындағы дәрістер, 182, Springer-Verlag, 1-17 бет, CiteSeerX  10.1.1.36.4265, дои:10.1007 / bfb0036046, ISBN  978-3540558514pdf
  2. ^ «3GPP RAN1 отырысы № 87 қорытынды есеп». 3GPP. Алынған 31 тамыз 2017.
  3. ^ Арикан, Эрдал (2009). «Арналарды поляризациялау: симметриялы екілік кірісті жадсыз арналар үшін сыйымдылыққа жету кодтарын құру әдісі - IEEE журналдары мен журналы». Ақпараттық теория бойынша IEEE транзакциялары. 55 (7): 3051–3073. arXiv:0807.3917. дои:10.1109 / TIT.2009.2021379. hdl:11693/11695.
  4. ^ Мюллер, Дэвид Э. (1954). «Буль алгебрасын коммутация тізбегін жобалауға және қателерді анықтауға қолдану». I.R.E операциялары Электрондық компьютерлер бойынша кәсіби топ. EC-3 (3): 6–12. дои:10.1109 / irepgelc.1954.6499441. ISSN  2168-1740.
  5. ^ Рид, Ирвинг С. (1954). «Бірнеше қателерді түзететін кодтар класы және декодтау схемасы». Ақпараттық теория бойынша IRE кәсіби тобының операциялары. 4 (4): 38–49. дои:10.1109 / тит.1954.1057465. hdl:10338.dmlcz / 143797. ISSN  2168-2690.
  6. ^ Прахладх Харша және басқалар, Жақындау алгоритмдерінің шектері: PCP және бірегей ойындар (DIMACS оқулық дәрістері), 5.2.1 бөлім.
  7. ^ Trellis and Turbo Coding, C. Schlegel & L. Perez, Wiley Interscience, 2004, p149.

Әрі қарай оқу

Сыртқы сілтемелер