Кіріспе

Қателерді түзететін код класы. Кодтау теориясында сызықтық код – код сөздерінің кез келген сызықтық комбинациясы да код сөз болып табылатын қателерді түзететін код. Сызықтық кодтар дәстүрлі түрде блоктық кодтар мен конволюциялық кодтарға бөлінеді, бірақ турбо кодтарды осы екі түрдің гибриді ретінде қарастыруға болады. Сызықтық кодтар басқа кодтарға қарағанда тиімді кодтау және декодтау алгоритмдерін пайдалануға мүмкіндік береді (мысалы, синдромдық декодтау). Сызықтық кодтар алдын ала қателерді түзетуде қолданылады және байланыс арнасында символдарды (мысалы, биттерді) беру әдістерінде қолданылады, сондықтан байланыс кезінде қателер пайда болған жағдайда, хабарлама блогын алған адам кейбір қателерді түзетуге немесе анықтауға мүмкіндік алады. Сызықтық блок кодтағы код сөздері – жіберілетін бастапқы мәннен көп символдарды пайдалана отырып кодталған символдар блогы. Ұзындығы n сызықтық код n символы бар блокты береді. Мысалы, [7,4,3] Хамминг коды – 7 биттік код сөздерді пайдалана отырып 4 биттік хабарламаны көрсететін сызықтық екілік код. Екі түрлі код сөз кем дегенде үш бит бойынша өзгеше болады. Осының салдарынан әр код сөз үшін екі қате анықталады, ал бір қате түзетіледі. Бұл кодта 2⁴=16 код сөз бар.

Анықтама және параметрлер

Ұзындығы n және өлшем k сызықтық код – бұл q элементі бар шекті өрістегі векторлық кеңістіктің өлшем k сызықтық C субкеңістігі. Мұндай код q-дық код деп аталады. Егер q = 2 немесе q = 3 болса, код тиісінше екілік код немесе үштік код ретінде сипатталады. C-дегі векторлар кодтық сөздер деп аталады. Кодтың мөлшері – кодтық сөздердің саны және ол qk-ға тең. Кодтық сөздің салмағы – оның нөлден өзге элементтерінің саны, ал екі кодтық сөздің арасындағы қашықтық – олардың арасындағы Хамминг қашықтығы, яғни олардың өзгеше элементтерінің саны. Сызықтық кодтың d қашықтығы – оның нөлдік емес кодтық сөздерінің ең кіші салмағы немесе, эквивалентті түрде, ерекше кодтық сөздер арасындағы ең кіші қашықтық. Ұзындығы n, өлшем k және қашықтығы d сызықтық кодты [n,k,d] код (немесе, дәлірек айтқанда, код) деп атайды. Біз стандартты базисті беруді қалаймыз, себебі әрбір координата "шулы канал" арқылы берілетін "битті" көрсетеді, онда берілу қатесінің ықтималдығы шағын (бинарлық симметриялық канал). Егер басқа базис қолданылса, онда бұл модель қолданылмайды және Хамминг метрикасы берілудегі қателер санын біз қалағандай өлшемейді.

Генератор және тексеру матрицалары

Сызықтық кеңістіктің кіші кеңістігі ретінде бүкіл код C (өте үлкен болуы мүмкін) кодтық сөздер жиынының аралығы ретінде көрсетіледі (сызықтық алгебрада негіз деп аталады). Бұл негізгі кодтық сөздер көбінесе G матрицасының, C кодының генерациялық матрицасы ретінде белгілі қатарларында топтастырылады. Егер G матрицасы блоктық түрде жазылса, мұнда I – бірлік матрицаны білдіреді, ал P – кез келген матрица болса, онда G матрицасы стандартты түрде деп айтылады. С ядросы С болатын сызықтық функцияны көрсететін H матрицасы C кодының тексеру матрицасы (немесе кейде тепе-теңдік тексеру матрицасы) деп аталады. Балама түрінде, H – С кодының нөлдік кеңістігі бар матрица. Егер C коды стандартты түрдегі G генерациялық матрицасын құраса, онда H – C кодының тексеру матрицасы болады. H матрицасы арқылы құрылған код C кодының дуалды коды деп аталады. G матрицасы m x n өлшемді, ал H матрицасы n x m өлшемді екенін тексеруге болады. Сызықтылық, кодтық сөз c₀ мен басқа кез келген кодтық сөз c ≠ c₀ арасындағы ең аз Хамминг қашықтығы d, c₀-дан тәуелсіз екендігіне кепілдік береді. Бұл C кодындағы екі кодтық сөздің айырмасы c − c₀ да кодтық сөз болып табылады (яғни C кіші кеңістігінің мүшесі) және d(c, c₀) = d(c − c₀, 0) қасиеттерінен туындайды. Осы қасиеттер мынаны білдіреді:

Басқаша айтқанда, сызықтық кодтың кодтық сөздері арасындағы ең аз қашықтықты анықтау үшін тек нөлдік емес кодтық сөздерді қарау жеткілікті. Ең аз салмаққа ие нөлдік емес кодтық сөз нөлдік кодтық сөзден ең аз қашықтықта болады, демек кодтың ең аз қашықтығын анықтайды. Сызықтық кодтың d қашықтығы H тексеру матрицасының сызықтық тәуелді бағандарының ең аз санына тең.

Дәлелдеме: себебі , бұл теңдесімен өрнектеледі, мұнда i – i-ші бағанды білдіреді. Бағандарынан алынғандардың барлығын жойсақ, қалғандары сызықтық тәуелді болады. Сондықтан, сызықтық тәуелді бағандардың саны кеміндегіше осыған тең. Екінші жағынан, сызықтық тәуелді бағандардың ең аз жиынтығын қарастырайық, мұнда I – баған индекстерінің жиыны. Енді мынадай векторды қарастырайық: егер , себебі , сондықтан , демек , бұл сызықтық тәуелді бағандардың ең аз саны. Осылайша, дәлелделген қасиет растыққа сәйкес келеді.

Мысал: Хамминг кодтары

Хамаң кодтары қателерді түзету мақсатында жасалған сызықтық кодтардың алғашқы түрі ретінде, сандық байланыс жүйелерінде кеңінен қолданылып келеді. Кез келген оң бүтін сан үшін Хамаң коды болады. Егер , онда бұл Хамаң коды 1 биттік қатені түзете алады. Мысал: Төмендегі генераторлық матрицасы және паритеттік тексеру матрицасы бар сызықтық блок коды – Хамаң коды.

Ең жақын көрші алгоритмі

d параметрі кодтың қателерді түзету қабілетімен тығыз байланысты. Келесі құрылым/алгоритм оны көрсетеді (ең жақын көрші декодтау алгоритмі деп аталады): Кіріс: v қабылданған вектор. Шығыс: егер бар болса, қабылданған векторға ең жақын кодты сөз . Бастапқыда келесі екі қадамды қайталаңыз. Қабылданған сөздің (Хэмминг) радиусы d-ге тең шар айналасындағы элементтерді тізімдеңіз, бұл R деп белгіленеді. R-дегі әрбір x үшін, егер x кодты сөз болса, оны шешім ретінде қайтарыңыз. Табу мүмкін болмаса, санау аяқталғанша және шешім табылмағанша қайталаңыз. Сызықтық код d қателерді түзетуге қабілетті деп аталады, егер әрбір қабылданған вектор үшін R ішінде бір ғана кодты сөз болса.

Халықтық жазу

Жалпы кодтар көбінесе C әрпімен белгіленеді, ал ұзындығы n және рангі k код (яғни, негізінде n код сөзі және генерациялық матрицасында k қатар бар) әдетте (n, k) код деп аталады. Сызықтық блок кодтары жиі [n, k, d] кодтары ретінде белгіленеді, мұнда d – кез келген екі код сөзі арасындағы ең кішкентай Хамминг қашықтығын көрсетеді. ([n, k, d] белгісін ұзындығы n, M мөлшері (яғни M код сөзі бар) және ең кішкентай Хамминг қашықтығы d болатын сызықты емес кодты белгілеу үшін қолданылатын (n, M, d) белгісімен шатастырмау керек.)

Жалғыз қайықты

Лемма (Синглтон шегі): Кез келген сызықтық [n,k,d] коды C үшін келесі шарт орындалады. k+d=n+1 шартын қанағаттандыратын код C ең үлкен арақашықтықпен ажыратылатын, немесе MDS код деп аталады. Мұндай кодтар, егер бар болса, белгілі бір мағынада ең жақсы кодтар болып табылады. Егер C1 және C2 ұзындығы n екі код болса және симметриялық топ Sn-де p пермутациясы бар болса, онда (c1, ..., cn) C1 кодында болса және тек қана (cp(1), ..., cp(n)) C2 кодында болса, онда C1 және C2 кодтары пермутациялық эквивалентті деп айтылады. Көбірек жалпылаған түрде, егер C1 кодын C2 кодына изоморфты түрде бейнелейтін мономиалды матрица болса, онда C1 және C2 кодтары эквивалентті деп айтылады. Лемма: Кез келген сызықтық код пермутациялық түрлендіру арқылы стандартты түрдегі кодқа эквивалентті болады.

Бонизоли теоремасы

Код теңқашықты деп аталады, егер және тек егер, кез келген екі түрлі кодтық сөздерінің арасындағы қашықтыққа тұрақты d саны тең болса. 1984 жылы Ариго Бонисоли шекті өрістердегі сызықтық бір салмақты кодтардың құрылымын анықтады және кез келген теңқашықты сызықтық кодтың қос Хамминг кодтарының тізбегі екенін дәлелдеді.

Жалпылау

Сонымен қатар, өрістік емес әліпбилердегі Хамминг кеңістіктері де қарастырылды, әсіресе шекті сақиналар үстінде, ең әйгілісі Z4 үстіндегі Галуа сақиналары. Бұл векторлық кеңістіктердің орнына модульдерді, ал сызықтық кодтардың орнына сақиналық сызықтық кодтарды (қосалқы модульдермен теңестіріледі) тудырады. Мұндай жағдайда қолданылатын әдеттегі метрика – Ли қашықтығы. (яғни GF(22m)) Хамминг қашықтығымен және (GR(4,m) деп те белгіленеді) Ли қашықтығымен арасында Грей изометриясы бар; оның ең басты артықшылығы – бұл GF(22m) үстінде сызықтық емес кейбір "жақсы" кодтар мен сақиналық сызықтық кодтардың сәйкестігін орнату. Жақында кейбір авторлар мұндай сақиналар үстіндегі кодтарды да сызықтық кодтар деп атайды.