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

Зьвесткі зь Вікіпэдыі — вольнай энцыкляпэдыі.

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

Зьмест

[рэдагаваць] Спосабы карэкцыі памылак

[рэдагаваць] Патройнае мажарытаванне

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

[рэдагаваць] Карэктуючыя коды

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

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

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

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

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

[рэдагаваць] Блокавыя коды

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

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

Задаць блокавы код можна па-рознаму, у тым ліку табліцай, дзе кожнай сукупнасці з 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}.

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

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) = v0 + v1x + ... + vn − 1xn − 1. Пры гэтым цыклічны зрух кодавага слова эквівалентны множанню палінома на x па модулі xn − 1.

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

[рэдагаваць] Генератарны паліном

Можна паказаць, што ўсе кодавыя словы пэўнага цыклічнага кода кратныя вызначанаму генератарнага паліному g(x). Генератарны паліном з'яўляецца дзельнікам xn − 1.

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

  • несістэматычнае кадаванне здзяйсняецца шляхам множання кадаванага вектара на g(x): v(x) = u(x)g(x);
  • сістэматычнае кадаванне здзяйсняецца шляхам «дапісання» да кадаванага слова астатка ад дзялення xnku(x) на g(x), гэта значыць v(x) = xnku(x) + [xnku(x)modg(x)].

[рэдагаваць] Коды CRC

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

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

назоў кода ступень паліном
CRC-12 12 x12 + x11 + x3 + x2 + x + 1
CRC-16 16 x16 + x15 + x2 + 1
CRC-CCITT 16 x16 + x15 + x5 + 1
CRC-32 32 x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

[рэдагаваць] Коды БЧХ

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

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

[рэдагаваць] Коды Рыда-Саламона

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

[рэдагаваць] Перавагі і недахопы блокавых кодаў

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

[рэдагаваць] Згорткавыя коды

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

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

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

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

[рэдагаваць] Перавагі і недахопы згорткавых кодаў

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

[рэдагаваць] Каскаднае кадаванне. Турба-коды

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

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

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

[рэдагаваць] Адзнака эфектыўнасці кодаў

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

[рэдагаваць] Мяжа Хэмінга і дасканалыя коды

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

\sum_{i=0}^t C_n^i \le 2^{n-k}.

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

[рэдагаваць] Энергетычны выйгрыш

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

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

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

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

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

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