Карэкцыя памылак

Карэ́кцыя памы́лак — дзеяньне, накіраванае на аднаўленьне фрагмэнтаў зьвестак, скажоных пры запісе/прайграваньні інфармацыі або пры яе перадачы па лініях сувязі. У большасьці выпадкаў выкарыстоўваюцца карэктуючыя коды (коды, што выпраўляюць памылкі, коды з карэкцыяй памылак, завадаўстойлівыя коды).

Спосабы карэкцыі памылак

Патройнае мажарытаваньне

Адным з самых простых і надзейных (і неэфэктыўных праз выдаткі) спосабаў карэкцыі зьяўляецца патройнае мажарытаваньне, сутнасьць якога ў тым, што зьвесткі перадаюцца тры разы, а на прыёмным баку адбываецца простае галасаваньне па трох прынятых адліках. Напрыклад, калі патрабуецца перадаць «1», то ў канал сувязі паступіць «111», у выніку скажэньняў можа быць прынята, напрыклад, «101», а пасьля галасаваньня атрымаецца «1» (бо ў радку «101» адзінак больш, чым нулёў).

Карэктуючыя коды

Карэктуючыя коды — коды для выяўленьня або выпраўленьня памылак, што ўзьнікаюць пры перадачы інфармацыі пад уплывам завадаў, а таксама пры яе захоўваньні.

Для гэтага пры запісе (перадачы) ў карысныя зьвесткі дадаюць адмысловай структуры залішнюю інфармацыю, а пры чытаньні (прыёме) яе выкарыстаюць для таго, каб выявіць або выправіць памылкі. Натуральна, што лік памылак, якія магчыма выправіць, абмежаваны і залежыць ад пэўнага ўжытага коду.

З кодамі, якія выпраўляюць памылкі, цесна зьвязаныя коды выяўленьня памылак. У адрозьненьне ад першых, апошнія могуць толькі ўсталяваць факт наяўнасьці памылкі ў перададзеных зьвестках, але ня выправіць яе.

У рэчаісьнасьці коды выяўленьня памылак належаць да тае ж клясы кодаў, што і коды, якія выпраўляюць памылкі. Больш за тое, любы код, які выпраўляе памылкі, можа быць скарыстаны і для выяўленьня памылак. Таму мае сэнс разглядаць гэтыя паняцьці разам.

Па спосабе працы са зьвесткамі коды, якія выпраўляюць памылкі, падзяляюцца на блёкавыя, якія дзеляць інфармацыю на фрагмэнты сталай даўжыні і апрацоўваюць кожны зь іх паасобку, і згорткавыя, якія працуюць са зьвесткамі як зь бесьперапыннай плыняй.

Блёкавыя коды

Няхай кадаваная інфармацыя дзеліцца на фрагмэнты даўжынёй $k$ біт, якія пераўтворацца ў кодавыя словы даўжынёй $n$ біт. Тады адпаведны блёкавы код звычайна пазначаюць $(n,k)$ . Пры гэтым лік $R={\frac {k}{n}}$ завецца хуткасьцю коду.

Калі зыходныя $k$ біт код пакідае нязьменнымі і дадае $n-k$ праверачных, такі код завецца сыстэматычным, інакш несыстэматычным.

Задаць блёкавы код можна па-рознаму, у тым ліку табліцай, дзе кожнай сукупнасьці зь $k$ інфармацыйных біт супастаўляецца $n$ біт кодавага слова. Аднак добры код павінны адпавядаць, як мінімум, наступным крытэрам:

здольнасьць выпраўляць як мага большую колькасьць памылак;
як мага меншая памернасьць;
прастата кадаваньня і дэкадаваньня.

Няцяжка бачыць, што прыведзеныя патрабаваньні супярэчаць адно аднаму. Менавіта таму існуе вялікая колькасьць кодаў, кожны зь якіх прыдатны для свайго кола задачаў.

Практычна ўсе коды зьяўляюцца лінейнымі. Гэта зьвязана з тым, што нелінейныя коды значна складаней дасьледаваць, і для іх цяжка забясьпечыць прымальную лёгкасьць кадаваньня і дэкадаваньня.

Лінейныя коды агульнага выгляду

Лінейны блёкавы код — такі код, што мноства яго кодавых слоў утворыць $k$ -мерную лінейную падпрастору (назавем яе $C$ ) у $n$ -мернай лінейнай прасторы, ізаморфнай прасторы $k$ -бітных вэктараў.

Гэта значыць, што апэрацыя кадаваньня адпавядае множаньню зыходнага $k$ -бітнага вэктару на нявыраджаную матрыцу $G$ .

Хай $C^{\perp }$ — артаганальная падпрастора ў дачыненьні да $C$ , а $H$ — матрыца, задае базіс гэтай падпрасторы. Тады для любога вэктару ${\overrightarrow {v}}\in C$ справядліва:

{\overrightarrow {v}}H^{T}={\overrightarrow {0}}

.

Мінімальная адлегласьць і карэктуючая здольнасьць

Адлегласьцю Хэмінга (мэтрыкай Хэмінга) паміж двума кодавымі словамі ${\overrightarrow {v_{1}}}$ і ${\overrightarrow {v_{2}}}$ завецца колькасьць розных біт на адпаведных пазыцыях, гэта значыць лік «адзінак» у вэктары ${\overrightarrow {v_{1}}}\oplus {\overrightarrow {v_{2}}}$ .

Мінімальная адлегласьць Хэмінга ( $d_{min}$ ) зьяўляецца важнай характарыстыкай лінейнага блёкавага коду. Яна вызначае іншую, ня менш важную характарыстыку — карэктуючую здольнасьць:

t={\mathcal {b}}{\frac {d_{min}-1}{2}}{\mathcal {c}}

, тут кутнія дужкі пазначаюць акругленьне «уніз».

Карэктуючая здольнасьць вызначае, колькі памылак код можа гарантавана выправіць.

Растлумачым на прыкладзе. Выкажам здагадку, што ёсьць два кодавыя словы A і B, адлегласьць Хэмінга паміж імі роўная 3. Калі было перададзенае слова A, і канал занёс памылку ў адным біце, яна можа быць выпраўленая, бо нават у гэтым выпадку прынятае слова бліжэй да кодавага слова A, чым B. Але калі каналам былі занесеныя памылкі ў двух бітах, дэкодэр можа палічыць, што было перададзенае слова B.

Коды Хэмінга

Коды Хэмінга — найпрасьцейшыя лінейныя коды зь мінімальнай адлегласьцю 3, гэта значыць здольныя выправіць адну памылку. Код Хэмінга можа быць прадстаўлены ў такім выглядзе, што сындром

{\overrightarrow {s}}={\overrightarrow {r}}H^{T}

, дзе

{\overrightarrow {r}}

— прыняты вэктар,

будзе роўны нумару пазыцыі, у якой адбылася памылка. Гэтая ўласьцівасьць дазваляе зрабіць дэкадаваньне вельмі простым.

Агульны мэтад дэкадаваньня лінейных кодаў

Любы код (у тым ліку нелінейны) можна дэкадаваць з дапамогай звычайнай табліцы, дзе кожнаму значэньню прынятага слова ${\overrightarrow {r_{i}}}$ адпавядае найболей верагоднае перададзенае слова ${\overrightarrow {u_{i}}}$ . Аднак, гэты мэтад патрабуе ўжываньня вялізных табліц ужо для кодавых словаў параўнальна невялікай даўжыні.

Для лінейных кодаў гэты мэтад можна істотна спрасьціць. Пры гэтым для кожнага прынятага вэктару ${\overrightarrow {r_{i}}}$ вылічаецца сындром ${\overrightarrow {s_{i}}}={\overrightarrow {r_{i}}}H^{T}$ . Паколькі ${\overrightarrow {r_{i}}}={\overrightarrow {v_{i}}}+{\overrightarrow {e_{i}}}$ , дзе ${\overrightarrow {v_{i}}}$ — кодавае слова, а ${\overrightarrow {e_{i}}}$ — вэктар памылкі, то ${\overrightarrow {s_{i}}}={\overrightarrow {e_{i}}}H^{T}$ . Затым з дапамогай табліцы па сындроме вызначаецца вэктар памылкі, з дапамогай якога вызначаецца перададзенае кодавае слова. Пры гэтым табліца атрымліваецца значна меншая, чым пры выкарыстаньні папярэдняга мэтаду.

Лінейныя цыклічныя коды

Нягледзячы на тое, што дэкадаваньне лінейных кодаў ужо значна прасьцейшае за дэкадаваньне большасьці нелінейных, для большасьці кодаў гэты працэс усё яшчэ досыць складаны. Цыклічныя коды, акрамя прасьцейшага дэкадаваньня, валодаюць і іншымі важнымі ўласьцівасьцямі.

Цыклічным кодам зьяўляецца лінейны код, які валодае наступнай уласьцівасьцю: калі ${\overrightarrow {v}}$ зьяўляецца кодавым словам, то яго цыклічная перастанова таксама зьяўляецца кодавым словам.

Словы цыклічнага коду зручна ўяўляць у выглядзе паліномаў. Напрыклад, кодавае слова ${\overrightarrow {v}}=(v_{0},v_{1},...,v_{n-1})$ уяўляецца ў выглядзе паліному $v(x)=v_{0}+v_{1}x+...+v_{n-1}x^{n-1}$ . Пры гэтым цыклічны зрух кодавага слова эквівалентны множаньню паліному на $x$ па модулі $x^{n}-1$ .

У далейшым, калі не паказанае іншае, мы будзем лічыць, што цыклічны код зьяўляецца двайковым, гэта значыць $v_{0},v_{1}$ … могуць прымаць значэньні 0 або 1.

Генэратарны паліном

Можна паказаць, што ўсе кодавыя словы пэўнага цыклічнага коду кратныя вызначанаму генэратарнага паліному $g(x)$ . Генэратарны паліном зьяўляецца дзельнікам $x^{n}-1$ .

З дапамогай генэратарнага паліному зьдзяйсьняецца кадаваньне цыклічным кодам. У прыватнасьці:

несыстэматычнае кадаваньне зьдзяйсьняецца шляхам множаньня кадаванага вэктару на $g(x)$ : $v(x)=u(x)g(x)$ ;

сыстэматычнае кадаваньне зьдзяйсьняецца шляхам «дапісаньня» да кадаванага слова астачы ад дзяленьня $x^{n-k}u(x)$ на $g(x)$ , гэта значыць $v(x)=x^{n-k}u(x)+[x^{n-k}u(x)modg(x)]$ .

Коды CRC

Коды CRC (cyclic redundancy check — цыклічная залішняя праверка) зьяўляюцца сыстэматычнымі кодамі, прызначанымі ня для выпраўленьня памылак, а для іх выяўленьня. Яны выкарыстаюць спосаб сыстэматычнага кадаваньня, выкладзены вышэй: «кантрольная сума» вылічаецца шляхам дзяленьня $x^{n-k}u(x)$ на $g(x)$ . З прычыны таго, што выпраўленьне памылак не патрабуецца, праверка правільнасьці перадачы можа праводзіцца гэтаксама.

Такім чынам, від паліному g(x) задае пэўны код CRC. Прыклады найбольш папулярных паліномаў:

назва коду	ступень	паліном
CRC-12	12	$x^{12}+x^{11}+x^{3}+x^{2}+x+1$
CRC-16	16	$x^{16}+x^{15}+x^{2}+1$
CRC-CCITT	16	$x^{16}+x^{15}+x^{5}+1$
CRC-32	32	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$

Коды БЧХ

Коды Боўза-Чаўдхуры-Хаквінгема (БЧХ) зьяўляюцца падклясай двайковых цыклічных кодаў. Іх адметная ўласьцівасьць — магчымасьць пабудовы коду БЧХ зь мінімальнай адлегласьцю ня менш за зададзеную. Гэта важна з той прычыны, што вызначэньне мінімальнай адлегласьці коду, увогуле, зьяўляецца вельмі складанай задачай.

Матэматычна пабудова кодаў БЧХ і іх дэкадаваньне выкарыстоўваюць раскладаньне генэратарнага паліному $g(x)$ на множнікі ў полі Галуа.

Коды Рыда-Салямона

Коды Рыда-Салямона (РС-коды) фактычна зьяўляюцца недвайковымі кодамі БЧХ, гэта значыць элемэнты кодавага вэктару зьяўляюцца ня бітамі, а групамі бітаў. Вельмі распаўсюджаныя коды Рыда-Салямона, якія працуюць з байтамі (актэтамі).

Перавагі і недахопы блёкавых кодаў

Хоць блёкавыя коды, як правіла, добра спраўляюцца з рэдкімі, але вялікімі пачкамі памылак, іх эфэктыўнасьць пры частых, але невялікіх памылках (напрыклад, у канале з адытыўным белым шумам (АБГШ)), менш высокая.

Згорткавыя коды

Згорткавыя коды, у адрозьненьне ад блёкавых, ня дзеляць інфармацыю на фрагмэнты і працуюць зь ёй як з суцэльнай плыньню зьвестак.

Згорткавыя коды, як правіла, спараджаюцца дыскрэтнай лінейнай інварыянтнай у часе сыстэмай. Таму, у адрозьненьне ад большасьці блёкавых кодаў, згорткавае кадаваньне — вельмі простая апэрацыя, чаго нельга сказаць пра дэкадаваньне.

Кадаваньне згорткавым кодам выконваецца з дапамогай рэгістра зруху, адводы ад якога сумуюцца па модулі два. Такіх сумаў можа быць дзьве (часьцей за ўсё) або больш.

Дэкадаваньне згорткавых кодаў, як правіла, выконваецца па альгарытму Вітэрбі, які спрабуе аднавіць перададзеную пасьлядоўнасьць паводле крытэру максымальнай праўдападобнасьці.

Перавагі і недахопы згорткавых кодаў

Згорткавыя коды эфэктыўна працуюць у канале зь белым шумам, але дрэнна спраўляюцца з пачкамі памылак. Больш за тое, калі дэкодэр памыляецца, на яго выхадзе заўсёды ўзьнікае пачак памылак.

Каскаднае кадаваньне. Турба-коды

Перавагі розных спосабаў кадаваньня можна аб’яднаць, ужыўшы каскаднае кадаваньне. Пры гэтым інфармацыя спачатку кадуецца адным кодам, а затым іншым.

Напрыклад, папулярнай зьяўляецца наступная канструкцыя: зьвесткі кадуюцца кодам Рыда-Салямона, затым перамяжоўваюцца (пры гэтым сымбалі, разьмешчаныя блізка, зьмяшчаюцца далёка) і кадуюцца згорткавым кодам. На прымачы спачатку дэкадуецца згорткавы код, затым зьдзяйсьняецца зваротнае перамяжэньне (пры гэтым пачкі памылак на выхадзе згорткавага дэкодэру трапляюць у розныя кодавыя словы коду Рыда-Салямона), і затым зьдзяйсьняецца дэкадаваньне коду Рыда-Салямона.

Некаторыя коды адмыслова сканструяваныя для ітэратыўнага дэкадаваньня, пры якім дэкадаваньне зьдзяйсьняецца ў некалькі праходаў, кожны зь якіх выкарыстае інфармацыю ад папярэдняга. Такія коды завуцца «турба-кодамі» і дазваляюць дабіцца вялікай эфэктыўнасьці, аднак, іх дэкадаваньне патрабуе вялікіх рэсурсаў.

Адзнака эфэктыўнасьці кодаў

Эфэктыўнасьць кодаў вызначаецца колькасьцю памылак, якія той можа выправіць, колькасьцю залішняй інфармацыі, даданьне якой патрабуецца, а таксама складанасьцю рэалізацыі кадаваньня і дэкадаваньні (як апаратнай, так і ў выглядзе праграмы для ЭВМ).

Мяжа Хэмінга і дасканалыя коды

Няхай маецца двайковы блёкавы $(n,k)$ код з карэктуючай здольнасьцю $t$ . Тады справядліва няроўнасьць (званая мяжой Хэмінга):

\sum _{i=0}^{t}C_{n}^{i}\leq 2^{n-k}

.

Коды, якія задавальняюць гэтай мяжы з роўнасьцю, завуцца дасканалымі. Да дасканалых кодаў неалежаць, напрыклад, коды Хэмінга. Часта коды, што ўжываюцца на практыцы, зь вялікай карэктуючай здольнасьцю (такія, як коды Рыда-Салямона) не зьяўляюцца дасканалымі.

Энэргетычны выйгрыш

Пры перадачы інфармацыі па канале сувязі імавернасьць памылкі залежыць ад адносінаў сыгнал/шум на ўваходзе дэмадулятару, такім чынам пры сталым узроўні шуму вырашальнае значэньне мае магутнасьць перадатніка. У сыстэмах спадарожнікавай і мабільнай, а таксама іншых тыпаў сувязі маецца вострае пытаньне эканоміі энэргіі. Акрамя таго, у некаторых сыстэмах сувязі (напрыклад, тэлефоннай) неабмежавана падвышаць магутнасьць сыгналу не даюць тэхнічныя абмежаваньні.

Паколькі завадаўстойлівае кадаваньне дазваляе выпраўляць памылкі, пры яго ужываньні магутнасьць перадатніка можна зьнізіць, пакідаючы хуткасьць перадачы інфармацыі нязьменнай. Энэргетычны выйгрыш вызначаецца як розьніца адносінаў с/ш пры наяўнасьці і адсутнасьці кадаваньня.

Ужываньне кодаў, якія выпраўляюць памылкі

Коды, якія выпраўляюць памылкі, ужываюцца:

у сыстэмах лічбавай сувязі, у тым ліку: спадарожнікавай, радыёрэлейнай, сотавай, перадачы зьвестак па тэлефонных каналах.
у сыстэмах захоўваньня інфармацыі, у тым ліку магнітных і аптычных.

Коды, якія выяўляюць памылкі, ужываюцца ў сеткавых пратаколах розных узроўняў.

Аўтаматычны запыт паўторнай перадачы

Сыстэмы з аўтаматычным запытам паўторнай перадачы (ARQ — Automatic Repeat reQuest) заснаваныя на тэхналёгіі выяўленьня памылак. Распаўсюджаныя наступныя мэтады аўтаматычнага запыту:

Запыт ARQ з прыпынкамі (stop-and-wait ARQ)

Ідэя гэтага мэтаду складаецца ў тым, што перадатнік чакае ад прымача пацьверджаньня пасьпяховага прыёму папярэдняга блёку зьвестак перад тым як пачаць перадачу наступнага. У выпадку, калі блёк зьвестак быў прыняты з памылкай, прымач перадае адмоўнае пацьверджаньне (negative acknowledgement, NAK), і перадатник паўтарае перадачу блёку. Гэты мэтад падыходзіць для паўдуплекснага каналу сувязі. Яго недахопам зьяўляецца нізкая хуткасьць праз высокія накладныя выдаткі на чаканьне.

Бесьперапынны запыт ARQ са зваротам (continuous ARQ with pullback)

Для гэтага мэтаду неабходны поўнадуплексны канал. Перадача зьвестак ад перадатніка да прымача зьдзяйсьняецца адначасова. У выпадку памылкі перадача аднаўляецца, пачынаючы з хібнага блёку (гэта значыць, перадаецца хібны блёк і ўсё наступныя).

Бесьперапынны запыт ARQ з выбарковым паўторам (continuous ARQ with selective repeat)

Пры гэтым падыходзе ажыцьцяўляецца перадача толькі хібна прынятых блёкаў зьвестак.

Глядзіце таксама

Літаратура

Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2005. — ISBN 5-94836-035-0