Выяўленне і выпраўленне памылак

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

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

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

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

Адным з самых простых і надзейных (і неэфектыўных праз выдаткі) спосабаў карэкцыі з'яўляецца патройнае мажарытаванне, сутнасць якога ў тым, што дадзеныя перадаюцца тры разы, а на прыёмным баку адбываецца простае галасаванне па трох прынятых адліках. Напрыклад, калі патрабуецца перадаць «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