Kontrollo matricën. Gjenerimi i matricave të kodeve të bllokut

Prezantimi

Përshkrimi i procesit të komunikimit dixhital

Burimi lëshon një mesazh që përfaqëson në rast i përgjithshëm disa sinjal elektrik... Ky sinjal konvertohet në formë dixhitale, i cili është i përshtatshëm për përpunim të mëtejshëm.

Më pas, informacioni kompresohet (kodimi i burimit), i cili minimizon tepricën e mesazhit. Kodimi i burimit zvogëlon koston e transmetimit dhe ruajtjes së informacionit. Pas kësaj, mesazhi duhet të transmetohet përmes një kanali të zhurmshëm. Në mënyrë që mesazhi të arrijë te konsumatori në një formë të pashtrembëruar, përdoret kodimi i informacionit imun nga zhurma (kodimi i kanalit). Nga ana e konsumatorit, informacioni deshifrohet. Dekoderi i kanalit korrigjon gabimet në fjalën e marrë, dhe dekoderi burimor e konverton fjalën e korrigjuar në një formë të përshtatshme për konsumatorin.

Kur flitet për kodet që kontrollojnë gabimet, duhen dalluar dy strategji të përdorimit të tyre.

1. Korrigjimi i drejtpërdrejtë i gabimit për shkak të tepricës (Forward Error Correction - FEC).
2. Zbulimi i gabimit me kërkesat e mëvonshme për ritransmetim të informacionit të marrë gabimisht (Kërkesë për përsëritje automatike - ARQ).

Kur zgjedhin metodat e kodimit dhe dekodimit, ato udhëhiqen nga shumë faktorë, marrëdhënia e të cilave tregohet në figurë.

Kompleksiteti i përgjithshëm përfshin kostot e harduerit dhe softuerit për zbatimin e koduesit dhe dekoderit, koston e ruajtjes dhe transmetimit të informacionit, etj. Shkalla e rrjedhës së të dhënave përfshin transmetimin e informacionit të dobishëm, bitet e kontrollit, si dhe kërkesat dhe përsëritjet për këto kërkesat e blloqeve individuale të informacionit.

Kodimi kundër ndërhyrjes

Informacion i pergjithshem

Sistemet reale të transmetimit të të dhënave nuk janë perfekte. Duke aplikuar teknologjinë e informacionit, duhet të kemi parasysh mundësinë e gabimeve në transmetimin dhe ruajtjen e informacionit. Kjo kryesisht vlen për

• ruajtja e informacionit në media me densitet të lartë (media magnetike, CD-ROM, DVD);
• transmetimi i të dhënave me fuqi të kufizuar të sinjalit (satelit dhe lidhje celulare);
• transmetimi i informacionit përmes kanaleve shumë të zhurmshme (komunikim celular, me shpejtësi të lartë linja teli komunikimi);
• kanalet e komunikimit me kërkesa të rritura për besueshmërinë e informacionit ( rrjetet kompjuterike, linjat e transmetimit me kompresim të të dhënave).

Në të gjitha rastet e mësipërme, përdoren kodet e kontrollit të gabimeve.

Merrni parasysh modeli më i thjeshtë transmetimi i të dhënave duke përdorur kodimin e korrigjimit të gabimeve.

Lëreni koduesin burimor të nxjerrë në mënyrë sekuenciale fjalë informacioni me gjatësi fikse. Enkoderi i kanalit zëvendëson çdo fjalë informacioni u me një fjalë kodi v. Transmetuesi gjeneron sinjale që korrespondojnë me kodin v dhe i dërgon ato në kanal. Marrësi prodhon transformim i kundërt, si rezultat i së cilës fjala binare e marrë r dërgohet në dekoder. Dekoderi krahason fjalën e marrë r me të gjitha kodet e mundshme të kodit të përdorur. Nëse fjala r përkon me një nga fjalët e kodit, atëherë fjala informative përkatëse i dorëzohet konsumatorit. Nëse r ndryshon nga të gjitha fjalët e kodit, atëherë në kanal ka ndodhur një gabim i dallueshëm. Qëllimi i përdorimit të kodimit të kanalit është të arrihet një përputhje e transmetuarit fjalë informacioni u dhe fjala e informacionit të marrë u ′.

Nga të këtij përshkrimi Mund të nxirren 2 përfundime:

• Nëse, gjatë transmetimit përmes një kanali të zhurmshëm, një fjalë e koduar vendoset në një fjalë kodi tjetër që nuk përputhet me atë të transmetuar, ndodh një gabim i pazbulueshëm. Le ta quajmë atë gabimi i mbetur i dekodimit.
• Kërkohet ndërtimi i kodeve me një strukturë të caktuar matematikore, e cila bën të mundur njohjen në mënyrë efektive dhe, në disa raste, korrigjimin e gabimeve që lindin kur informacioni transmetohet përmes një kanali komunikimi.

Kodet e bllokut linear

Kodet lineare të blloqeve binare formojnë një familje të rëndësishme kodesh. Këto kode janë të shquar në atë që, duke përfaqësuar informacionin dhe fjalët kodike në formën e vektorëve binar, ne mund të përshkruajmë proceset e kodimit dhe dekodimit duke përdorur aparatin e algjebrës lineare. Në këtë rast, përbërësit e vektorëve dhe matricave që futen janë simbolet 0 dhe 1. Veprimet në komponentët binare kryhen sipas rregullave moduli aritmetik 2.

Kodi më i famshëm i linjës është kodi i bllokut Hamming. Më tej, përshkrimi i kodeve lineare të bllokut do të bëhet duke përdorur këtë kod si shembull. Në veçanti, do të merret parasysh kodi (7,4) Hamming.

Kodimi i kodit binar (n, k) harton një grup prej 2 k fjalësh të mundshme informacioni binare në një grup fjalësh kodike 2 k n-dimensionale. Në teorinë e kodimit, ekziston gjithmonë një korrespondencë një-për-një midis këtyre grupeve.

Në vend të k bitave të vektorit të informacionit, n bit të vektorit të kodit transmetohen në kanal. Në këtë rast, flitet për kodim të tepërt me një normë: R = n ⁄ k.

Sa më e ulët të jetë shpejtësia, aq më i madh është teprica e kodit dhe aq më të mëdha janë mundësitë për mbrojtje nga gabimet. Sidoqoftë, duhet të kihet parasysh se me një rritje të tepricës, rritet edhe kostoja e transferimit të informacionit.

Përshkrimi i proceseve të kodimit dhe dekodimit

Materiali fillestar për ndërtimin e konstruksioneve të kodit është një hapësirë ​​vektoriale binare n-dimensionale, në të cilën specifikohen operacionet aritmetike moduli 2. Një hapësirë ​​lineare k-dimensionale që përmban 2 k fjalë kode është e ngulitur në të. Kodi C është formuar duke përdorur 2 k kombinime të k vektorëve bazë linearisht të pavarur (g 1, ..., g k).

Këta vektorë formojnë rreshtat e matricës gjeneruese të kodit C.

Për një kod C, ekziston një kod i dyfishtë C d i tillë që produkti skalar i çdo çifti vektorësh, njëri prej të cilëve i përket hapësirës C dhe tjetri hapësirës C d, është gjithmonë zero. Kjo do të thotë se vektorët e kodit C d janë ortogonal me vektorët e kodit C. Nga ana tjetër, nëse një vektor është ortogonal me të gjithë vektorët e kodit C, atëherë ai i përket kodit C d dhe anasjelltas. . Nënhapësira e dyfishtë vektoriale "përfshihet" nga n - k vektorë të bazuar linearisht të pavarur (h 1,…, h n - k). Këta vektorë formojnë rreshtat e matricës së kontrollit të barazisë.

Konsideroni një shembull të një matrice gjeneruese dhe kontrolluese të barazisë për një kod Hamming (7,4):

Duhet të theksohet një veti e rëndësishme: si matricat gjeneruese ashtu edhe ato të barazisë përmbajnë matricën e identitetit. Kjo veti përdoret në proceset e kodimit dhe dekodimit.

Kodimi

Fjala koduese v dhe fjala e informacionit u lidhen me raportin:

ku G është matrica gjeneruese, struktura e së cilës u përshkrua më sipër.

Për shembull, vektori i informacionit u = (1010) lidhet me vektorin e kodit si më poshtë:

Është e lehtë të shihet se katër bitet e fundit të vektorit të kodit përkojnë me vektorin e informacionit. Kjo veti quhet konsistenca e kodit.

Kodet në të cilat një fjalë informacioni mund të nxirret drejtpërdrejt nga vektori i kodit përkatës quhen sistematike. Matrica gjeneruese e çdo kodi sistematik gjithmonë mund të reduktohet në formën e mëposhtme duke riorganizuar kolonat:

G k × n = (P k × (n - k) I k),

ku I k është matrica e identitetit k × k.

Kështu, është gjithmonë e mundur të veçohen informacionet dhe të kontrollohen simbolet në vektorin e kodit të kodit sistematik.

Roli i karaktereve të kontrollit dhe përdorimi i tyre do të shpjegohet në detaje më poshtë.

Dekodimi

Detyra e dekoderit është të rivendosë vektorin e informacionit të transmetuar duke përdorur strukturën e kodit, bazuar në fjalën e marrë r. Për kodin Hamming (7, 4) të konsideruar më sipër, mund të propozohet algoritmi i mëposhtëm i zbulimit të gabimeve. Meqenëse kodi i konsideruar është sistematik, ne shprehim secilin nga tre simbolet e barazisë në terma të simboleve të vektorit të informacionit:

V 0 = v 3 ⊕ v 5 ⊕ v 6
v 1 = v 3 ⊕ v 4 ⊕ v 5
v 2 = v 4 ⊕ v 5 ⊕ v 6

Nëse ndodh një gabim në kanal, atëherë në vektorin e marrë r të paktën një nga barazitë nuk do të përmbushet. Le t'i shkruajmë marrëdhëniet e marra të testit në formën e një sistemi ekuacionesh për përbërësit e vektorit r:

R 0 ⊕ r 3 ⊕ r 5 ⊕ r 6 = s 0
r 1 ⊕ r 3 ⊕ r 4 ⊕ r 5 = s 1
r 2 ⊕ r 4 ⊕ r 5 ⊕ r 6 = s 2

Kështu, nga tre kolonat e para të matricës gjeneruese G, kemi marrë një sistem prej tre ekuacionesh kontrolli. Nëse në sistemin e marrë të ekuacioneve të paktën një nga komponentët (s 0, s 1, s 2) nuk është i barabartë me zero, atëherë ka ndodhur një gabim në kanal.

Le të shkruajmë sistemin e ekuacioneve testuese në formë të përgjithshme. Për çdo kod sistematik me një matricë gjeneratori G, matrica e kontrollit të barazisë përcaktohet si më poshtë:

H (n - k) × n = (I n - k P T k × (n - k)).

Pastaj sistemi i ekuacioneve testuese mund të shkruhet në formë

Vektori s zakonisht quhet sindromë. Kështu, një gabim do të zbulohet nëse të paktën një nga komponentët s nuk është zero.

Si shembull, merrni parasysh dekodimin sindromik të kodit Hamming (7, 4). Kur transmetoni një fjalë informacioni u = (1010) në një kanal pa zhurmë, r = v = (0011010). Mund të sigurohemi që në këtë rast sindroma të jetë e barabartë me 0.

Nëse, për shembull, ndodh një gabim i vetëm në fjalën e koduar në pozicionin e katërt (r = (0010010)), atëherë rreshti i katërt i matricës së kontrollit të transpozuar është sindromi.

Pasi kalojmë nëpër të gjitha pozicionet e mundshme të një gabimi të vetëm, marrim tabelë e plotë sindromat e një gabimi të vetëm - një tabelë e korrespondencës së numrit të shifrës së gabuar me sindromën që rezulton.

Ju mund të shihni se gabimi në pozicionin i-të fjalë kodike korrespondon me sindromën e formuar nga kolona e i-të e matricës H. Duke qenë se të gjitha kolonat e matricës janë të ndryshme, ne mund të përdorim tabelën e sindromave për të korrigjuar një gabim të vetëm të paraqitur nga kanali.

Varietetet e gabimeve

Kodet e bllokut linear kanë 3 lloje gabimesh:

1. Gabim i njohur dhe i korrigjueshëm
   • Sindroma është e pranishme në tabelën e sindromave
   • Dekoderi njeh dhe korrigjon gabimin dhe më pas ia transmeton fjalën e duhur marrësit
2. Gabim i njohur
   • Fjala e marrë nuk përputhet me asnjë nga fjalët e koduara
   • Sindroma nuk është e pranishme në tabelën e sindromave
   • Dekoderi njeh gabimin dhe dërgon një kërkesë për të ritransmetuar fjalën e të dhënave.
3. Gabim i panjohur
   • Fjala e marrë përputhet me një nga fjalët e koduara (nuk përputhet me kodin origjinal)
   • Sindroma është 0
   • Dekoderi nuk e njeh gabimin dhe i jep konsumatorit një mesazh informacioni të gabuar

konkluzioni

Duhet të theksohet se efektiviteti i një kodi të veçantë varet nga zona e aplikimit të tij dhe, në veçanti, nga kanali i komunikimit. Nëse raporti sinjal-zhurmë në kanal është mjaft i madh, atëherë probabiliteti i një gabimi të vetëm është shumë herë më i lartë se probabiliteti i gabimeve të rendit më të lartë, prandaj, përdorimi i kodit Hamming me korrigjimin e një gabimi të vetëm në një kanal të tillë mund të jetë shumë efektiv. Nga ana tjetër, në kanalet ku mbizotërojnë gabime të shumta (për shembull, kanalet me zbehje), korrigjimi i gabimeve të vetme është i pakuptimtë. Në zgjedhje praktike e një kodi specifik të korrigjimit të gabimeve, është gjithashtu e nevojshme të merret parasysh shpejtësia e dekodimit të tij dhe kompleksiteti i zbatimit teknik të tij.

Letërsia

1. Werner M. Bazat e kodimit. - M .: Teknosferë, 2004.
2. Bleihut R. Teoria dhe praktika e kodeve të kontrollit të gabimeve. - M .: Mir, 1986.

Oleg Rybak

Në të vërtetë, është e vështirë të gjesh një shpjegim adekuat. Më shpesh, autorët supozojnë se lexuesi di shumë paraprakisht dhe nuk kërkojnë të shpjegojnë pika në dukje të thjeshta që përmbajnë thelbin. Shumë i lumtur që ndesha këtë material, sqarova diçka për veten time.

Kodet lineare kanë vetinë e mëposhtme:

Nga gjithë turma 2 k nga fjalët kodike të lejuara që formojnë një grup linear, mund të dallohen nënbashkësi k fjalë që kanë vetinë e pavarësisë lineare.

Pavarësia lineare do të thotë që asnjë nga fjalët e përfshira në nëngrupin e fjalëve kodike të pavarura lineare nuk mund të merret duke përmbledhur (duke përdorur një shprehje lineare) çdo fjalë tjetër të përfshirë në këtë nëngrup.

Në të njëjtën kohë, ndonjë nga fjalët kodike të lejuara mund të merret duke përmbledhur disa fjalë të pavarura lineare.

Kështu, ndërtimi i kombinimeve të kodit të një kodi linear shoqërohet me operacione lineare. Për të kryer operacione të tilla, është i përshtatshëm përdorimi i një aparati llogaritës matricë të zhvilluar mirë.

Për arsimin n Fjalët e koduara -bit nga fjalët e koduara me k-bit (enkodimi) përdorin një matricë, e cila quhet gjeneruese (gjeneruese).

Matrica gjeneruese merret duke shkruar k fjalë të pavarura në mënyrë lineare në një kolonë.

Le të shënojmë sekuencën e informacionit të koduar X dhe do ta shkruajmë në formën e një matrice rreshti || X || dimension 1* k, Për shembull:

|| X || = || 11001 ||, ku k = 5.

Një nga mënyrat për të ndërtuar një matricë gjeneruese (gjeneruese) është si më poshtë: Ndërtohet nga matrica e identitetit || Unë || dimension k * k dhe matricën e shifrave shtesë (të tepërta) që i janë caktuar në të djathtë || MDR || dimensionet k * r.

ku k=4

Kjo strukturë e OM siguron një kod sistematik.

Procedura për ndërtimin e matricës MDS do të diskutohet më poshtë.

7.4 Rendi i kodimit

Fjala e koduar KS fitohet duke shumëzuar matricën e sekuencës së informacionit || X || në matricën gjeneruese || OM ||:

Shumëzimi kryhet sipas rregullave të shumëzimit të matricës: (SO në SO)

Thjesht duhet të mbani mend se shtesa këtu është modulo 2.

për shembull, matrica gjeneruese

|| OM || = 0010 011

dhe vektori i rreshtit të sekuencës së informacionit

Meqenëse matrica që do të shumëzohet ka vetëm një rresht, shumëzimi thjeshtohet. Në këtë rast, duhet të caktohen rreshtat e matricës gjeneruese (gjeneruese). || OM || copa të matricës së sekuencës së informacionit || X || dhe shtoni ato rreshta të matricës gjeneruese (gjeneruese) që korrespondojnë me shifrat e njësive të matricës || X ||.

vini re, se || DK || = || X, DR ||,

ku || X || - sekuenca e informacionit (pasi shumëzuar me matricën e identitetit || Unë ||),

a || DR ||- shifra shtesë, në varësi të matricës së shifrave shtesë || MDR ||:

|| DR || = || X || * || MDR ||

7.5 Rendi i dekodimit

Si rezultat i transmetimit të fjalës së koduar përmes kanalit, ajo mund të shtrembërohet nga ndërhyrjet. Kjo do të shkaktojë kodin e pranuar || PKS || mund të mos përputhet me origjinalin || COP ||.

Shtrembërimi mund të përshkruhet duke përdorur formulën e mëposhtme:

|| PKS || = || KS || + || NË ||,

ku || NË ||- vektori i gabimit - matricë-rresht me dimension 1* n, Me 1 në ato pozicione ku ka ndodhur shtrembërimi.

Dekodimi bazohet në gjetjen e të ashtuquajturit identifikues ose sindromën e matricës së gabimit || OP || gjatësia r shifra ( r- numri i biteve shtesë ose të tepërta në fjalën e kodit).

Identifikuesi përdoret për të gjetur vektorin e vlerësuar të gabimit.

Identifikuesi gjendet me formulën e mëposhtme:

|| OP || = || PC || * || TPM ||,

ku || PC || - kodi i marrë dhe ndoshta i korruptuar;

|| TPM ||, - matrica e barazisë së transpozuar që përftohet nga matrica e mbushjes || MDR || duke ia caktuar matricën e njësive nga poshtë:

Shembull || TPM ||:

Për aq sa || PKS || = || KS || + || BO ||, formula e fundit mund të shkruhet si:

|| OP || = || KS || * || TPM || + || VO || * || TPM ||.

Konsideroni termin e parë.

|| DK ||është një matricë rreshtash, dhe e para k shifra - informative.

Le të provojmë tani se produkti i fjalës së koduar || COP || në || TPM || rezulton në një matricë zero ||0||.

Për aq sa || COP ||- rreshti i matricës, është i mundur një renditje e thjeshtuar e shumëzimit të matricave të konsideruara më sipër.

Prandaj, mandati i parë në

|| OP || = || KS || * || TPM || + || NË || * || TPM ||

gjithmonë e barabartë me zero dhe identifikuesi është plotësisht i varur nga vektori i gabimit || NË ||.

Nëse tani zgjedhim një matricë të tillë të kontrollit të barazisë TPM dhe si rrjedhim MDR në mënyrë që vektorë të ndryshëm të gabimit t'u përgjigjen identifikuesve të ndryshëm OP, atëherë nga këta identifikues do të mund të gjendet vektori i gabimit NË, dhe kështu korrigjoni këto gabime.

Korrespondenca e identifikuesve me vektorët e gabimit gjendet paraprakisht duke shumëzuar vektorët e gabimeve të korrigjueshme me TPM;

Kështu, aftësia e një kodi për të korrigjuar gabimet përcaktohet tërësisht nga || MDR ||. Për ndërtimin MDR për kodet që korrigjojnë gabimet e vetme, ju nevojiten në çdo rresht MDR të ketë të paktën 2 njësi. Në këtë rast, është gjithashtu e nevojshme që të ketë të paktën një ndryshim midis çdo dy rreshti MDR.

Kodi që morëm është i papërshtatshëm në atë që identifikuesi, megjithëse është i lidhur pa mëdyshje me numrin e bitit të shtrembëruar, pasi një numër nuk është i barabartë me të. Për të kërkuar një bit të shtrembëruar, duhet të përdorni një tabelë shtesë të korrespondencës midis identifikuesit dhe këtij numri. Kodet në të cilat identifikuesi si numër përcakton pozicionin e shifrës së shtrembëruar u gjetën dhe morën emrin Kodet Hamming.

Ndërtesa MDR sepse rasti i korrigjimit të gabimeve të shumta bëhet shumë më i ndërlikuar. Autorë të ndryshëm kanë gjetur algoritme të ndryshme për ndërtimin || MDR || për këtë rast, dhe kodet përkatëse emërtohen me emrat e autorëve të tyre.

Vetëm si shembull, ne kemi shqyrtuar kodet më të thjeshta të korrigjimit - një kod të thjeshtë kontrolli të barazisë që zbulon një gabim të vetëm në një sekuencë të marrë dhe një kod përsëritës blloku dhe kod cloud që korrigjojnë një gabim të vetëm duke përdorur një grup kontrollesh të barazisë. Në të gjitha kodet, në procesin e kodimit të korrigjimit të gabimeve, u formuan bit shtesë, të shtuar në kombinimin origjinal të kodit.

Le të vendosim rregullat formale (gjeneruese) sipas të cilave kryhet kodimi, d.m.th. konvertimi i sekuencës së informacionit në një fjalë kodi.

Mënyra më e thjeshtë për të përshkruar ose caktuar kodet e korrigjimit është në mënyrë tabelare, ku çdo sekuence informacioni thjesht i caktohet një fjalë kodi nga tabela e kodeve. Për shembull, për kodin më të thjeshtë me kontroll të barazisë, tabela e korrespondencës midis kombinimeve të burimit dhe kodit do të jetë si më poshtë:

Kjo mënyrë e përshkrimit të kodeve është e zbatueshme për çdo kod, jo vetëm linear. Megjithatë, për të mëdha për të permasa tabela e kodeve rezulton të jetë shumë i madh për t'u përdorur në praktikë.

Një mënyrë tjetër për të përcaktuar kodet lineare të bllokut është përdorimi i të ashtuquajturave sistemet e ekuacioneve gjeneruese, duke përcaktuar rregullin sipas të cilit shndërrohen karakteret e sekuencës së informacionit karakteret e kodit... Për të njëjtin shembull, sistemi i gjenerimit të ekuacioneve do të duket si ky:

Sidoqoftë, mënyra më e përshtatshme dhe intuitive për të përshkruar kodet lineare të bllokut është përcaktimi i tyre duke përdorur matricë gjeneruese, e cila është një formë kompakte e paraqitjes së sistemit të ekuacioneve testuese.

Blloku linear(l, / s) -kodi përcaktohet plotësisht nga matrica G me madhësi për të X P me elementë të matricës binare. Për më tepër, çdo fjalë kod është kombinim linear rreshtat e matricës G, dhe çdo kombinim linear i rreshtave G është një fjalë kodi.

Do të thirren kodet lineare të bllokut të përcaktuar nga matricat gjeneruese kodet e matricës. Paraqitja e zakonshme (kanonike) e matricës gjeneruese duket si kjo:

Për shembull, për kodin më të thjeshtë (4, 3) të kontrollit të barazisë, matrica gjeneruese do të duket si kjo:

Le T -(t 1; t 2, ..., t deri) do të jetë blloku i mesazheve që duhet të kodohet duke përdorur këtë kod.

Pastaj kodi përkatës U do

Duke marrë parasysh strukturën e matricës G karakteret e fjalëve të koduara dhe do të jetë kështu:

Me fjale te tjera, për të simbolet më të majta të fjalës së kodit përkojnë me simbolet e sekuencës së informacionit të koduar, dhe pjesa tjetër (n - te) karakteret janë kombinime lineare të karaktereve të sekuencës së informacionit.

Për shembull, nëse sekuenca e hyrjes së koduesit t == (10 1), më pas duke përdorur matricën gjeneruese kodi do të ndërtohet si më poshtë:

8 Komandanti dërgoi tre zbulues në rrugën e parë, tre në të dytën, dy në të tretën dhe vetë shkoi në të katërtën. Krijo një matricë gjeneruese për një kod të tillë.

Përgjigje: Sipas komplotit të detyrës, mesazhi i marrë nga komandanti personalisht nuk mund të shtrembërohet. Prandaj, ne do të kufizohemi në studimin e informacionit të transmetuar nga luftëtarët. Në një grup që niset përgjatë njërës prej rrugëve, çdo ushtar duhet t'i raportojë komandantit ose për zbulimin e një objekti (le të caktojmë një raport të tillë si "1"), ose për mungesën e një objekti ("0" ). Në mungesë të shtrembërimit, raportet e secilit luftëtar nga i njëjti grup duhet të jenë të njëjta. Prandaj:

Matrica mund të sillet në formën kanonike duke rinumëruar luftëtarët, d.m.th. në rrugën e parë duke dërguar luftëtarët e parë, të katërt dhe të pestë, në rrugën e dytë - të dytën, të gjashtën dhe të shtatën, në rrugën e tretë - luftëtarët e tretë dhe të tetë. Ne marrim matricën gjeneruese të mëposhtme:

Kodi i përcaktuar në këtë mënyrë quhet bllok linear sistematik(P,/ kod cj me kontrolle të përgjithshme të barazisë.

Matrica gjeneruese-kodi linear quhet matricë e madhësisë, rreshtat e së cilës janë vektorët bazë të saj.

Për shembull,

është matrica gjeneruese e kodit me dy fjalë (000, 011).

është gjeneratori për kodin B nga shembulli 6.3.

Ne e dimë se fjalët e koduara janë kombinime lineare të vektorëve bazë, d.m.th. rreshtat e matricës. Kjo do të thotë se fjalët mund të merren duke shumëzuar një vektor me një matricë. Pra, mesazhi shkruhet si vektor dhe kodi që i përgjigjet mesazhit llogaritet me formulë

Kështu, një vektor bitash kthehet në një sekuencë prej karaktere binare transmetohet përmes kanalit ose shkruhet në memorien e pajisjes së ruajtjes.

Le të kthehemi te problemi i dekodimit.

Supozoni se për disa vektor binar të gjitha fjalët kodike të kodit , kënaqin identitetin

në të cilën shënon produktin pika të vektorëve dhe.

Për një vektor të tillë themi se është ortogonal. Pasi kemi gjetur një vektor të tillë, ne mund të kontrollojmë, duke përdorur identitetin (6.2), nëse sekuenca e marrë nga kanali është një fjalë kodi.

Vini re se (6.2) është e vlefshme për të gjitha fjalët e koduara nëse është e vlefshme për vektorët bazë, d.m.th. nëse

ku mbishkrim T do të thotë transpozim.

Sa më shumë “kontrolle” të tilla të gjejmë, aq më shumë gabime do të mund të zbulojmë dhe korrigjojmë.

Ushtrimi 6.4... Vërtetoni se çeqet formojnë një hapësirë ​​lineare.

Kjo hapësirë ​​do të quhet hapësirë ​​ortogonale me një kod linear ose hapësirë ​​verifikimi.

Ushtrimi 6.5... Gjeni dimensionin hapësirë ​​lineareçeqe.

Për të përfunduar ushtrimin e fundit, duhet të vini re se matrica ka saktësisht kolona lineare të pavarura. Jo më shumë (pse?) Dhe jo më pak (pse?). Le të rregullojmë listën e numrave të këtyre kolonave dhe ta quajmë këtë grup numrash grup informacioni... Pak më vonë, kuptimi i këtij emri do të bëhet më i qartë. Ne zgjedhim në mënyrë arbitrare vlerat e vektorit në pozicionet që nuk përfshihen grup informacioni... Cilat duhet të jenë vlerat në pozicionet e grupit të informacionit për të përmbushur (6.3)? Për t'iu përgjigjur kësaj pyetjeje, është e nevojshme të zgjidhet një sistem ekuacionesh lineare, dhe sistemi ka vetëm vendim.

Një pasojë e këtij arsyetimi është teorema

Teorema. Dimensioni i hapësirës së kontrollit të një kodi linear është i barabartë me.

Ne e shkruajmë bazën e hapësirës së provës në formën e një matrice

thirrur matrica e kontrollit kodi.

Matricat e kontrollit dhe gjeneratorit lidhen me relacionin

Nga kjo lidhje shohim se për çdo fjalë kode ekziston

Ky identitet mund të përdoret si kriter që një sekuencë arbitrare t'i përkasë një kodi, d.m.th. për të zbuluar gabimet.

Duke ditur, mund të gjesh. Për të kuptuar se si ta bëni këtë, vini re se i njëjti kod mund të specifikohet nga matrica të ndryshme gjeneruese, duke zgjedhur bazën e hapësirës në mënyra të ndryshme. Për më tepër, duke zëvendësuar në çdo varg me ndonjë kombinim linear të këtij vargu me vargje të tjera, marrim një matricë të re gjeneruese të të njëjtit kod.

Ndërrimi i kolonave të matricës, në përgjithësi, çon në kod të ndryshëm, por ky kod tjetër nuk ndryshon në karakteristikat e tij nga ai origjinal. Quhen kode që ndryshojnë vetëm në numërimin e pozicioneve ekuivalente.

Është e qartë se për çdo kod ekziston një ekuivalent për të cilin pozicionet e para formojnë një grup informacioni, d.m.th. kolonat e para formojnë një matricë të madhësisë jo të degjeneruar. Duke zëvendësuar rreshtat me kombinime lineare të rreshtave (metoda Gauss), matrica që rezulton mund të reduktohet në formë

ku është matrica e rendit njësi dhe është matrica e disa madhësive.

Një matricë e formës (6.6) quhet matricë gjeneruese e reduktuar në mënyrë sistematike dhe quhet kodi përkatës sistematike... Kodimi për kodin sistematik është pak më i lehtë sesa për kodin pamje e përgjithshme:

, (6.7)

ato. në fjalën e kodit, pozicionet e para janë vetëm një kopje e sekuencës së informacionit, dhe pozicionet e mbetura (kontrolloni) fitohen duke shumëzuar vektorin e informacionit me një matricë të madhësisë, e cila ndonjëherë është dukshëm më e vogël se. Prandaj, informacioni mbi kodin sistematik merr në mënyrë të konsiderueshme më pak memorie sesa informacioni i përgjithshëm i kodit linear.

Për një kod sistematik me një matricë gjeneruese në formën (6.6), matrica e kontrollit të barazisë mund të llogaritet me formulën

Ushtrimi 6.6... Kontrolloni (6.7). Këshillë: për këtë ju duhet të zëvendësoni (6.8) dhe (6.6) në (6.4).

Si të gjeni matrica e kontrollit për kodin jo sistematik?

Shume e thjeshte. Është e nevojshme që matrica të sillet në një formë sistematike dhe të përdoret (6.7). Nëse kolonat e para të matricës gjeneruese formojnë një nënmatricë jo të degjeneruar (pozicionet e para formojnë një grup informacioni), atëherë operacione të tilla si ndërrimi i rreshtit dhe zëvendësimi i rreshtave me kombinime lineare rreshtash janë të mjaftueshëm për ta sjellë atë në një formë sistematike. Nëse jo, fillimisht do t'ju duhet të gjeni grupin e informacionit dhe të rinumëroni pozicionet në mënyrë që pozicionet e para të bëhen informuese.

Meqenëse, sipas përkufizimit, kodi linear (l, / c) i gjatësisë P sipër GF (q)është një nënhapësirë GF k (q) hapësirë ​​vektoriale GF n (q), atëherë duhet të ekzistojë një plotësues ortogonal i nënhapësirës GF k (q) kodi i linjës (shih nënparagrafin 1.7.1).

Le të jetë Н një matricë, rreshtat e së cilës korrespondojnë me vektorët bazë të komplementit ortogonal të një kodi linear g-ar me gjatësi C P. Pastaj për çdo vektor me, që i përkasin kodit, i drejtë:

Kushti (2.10) bën të mundur kontrollimin e anëtarësimit të një sekuence n arbitrare të elementeve GF (q) një kod të caktuar linear g-ary.

Nëse një vektor i një kodi linear ka një peshë Hamming sho, atëherë kjo do të thotë se ka simbole sho jozero në fjalën e koduar (sipas përkufizimit të një peshe Hamming, shih nënseksionin 2.1.4). Pastaj, sipas rregullave të shumëzimit të matricës, prodhimi i një vektori me vlerën w0 të peshës Hamming nga matrica H t korrespondon me një kombinim linear të kolonave sho të matricës N. Për më tepër, barazia (2.10) padyshim vlen nëse dhe vetëm nëse nuk ka kolona të matricës N janë të varura në mënyrë lineare.

Kështu, kushti për ekzistencën në grupin e fjalëve kodike të një kodi linear të një fjale kodi me peshën Hamming sho është prania në matricë. N kolona të varura në mënyrë lineare në numrin e sho. Nga kjo rrjedh gjithashtu se një kod linear ka një peshë minimale (shih nënseksionin 2.1.4) të paktën një vlerë w0 nëse dhe vetëm nëse ndonjë nga kolonat w0 - 1 të matricës H janë linearisht të pavarura. Prandaj, sipas pabarazisë (2.6), për të gjetur një kod linear me peshë minimale w0, duke korrigjuar t gabime, mjafton të gjesh matricën H, me të paktën sho - 1 = 2 -tçdo kolonë ishte linearisht e pavarur.

Le të hedhim një vështrim më të afërt në matricën N. Siç u përmend më lart, rreshtat e matricës N janë vektorët bazë të komplementit ortogonal të kodit linear. Nëse bashkësia e n-sekuencave formon një nënhapësirë ​​dimensioni te, atëherë komplementi ortogonal i kësaj nënhapësire do të ketë dimension PC(shih nënparagrafët 1.7.1 dhe 1.7.2). Dimensioni i nënhapësirës P- për të formojnë ndonjë PC vektorët bazë. Prandaj matrica N duhet të përmbajë PC vija të pavarura në mënyrë lineare.

Meqenëse matricat G dhe N i përkasin të njëjtës hapësirë ​​të n-sekuencave, pastaj numri i kolonave të matricës Nështë e barabartë me numrin e kolonave të matricës G. Kështu, matrica N ka madhësi (l - te) x l. Të gjitha kolonat e matricës H, siç është përmendur tashmë, formoni në mënyrë lineare grupe të pavarura në 2t kolonat.

Sipas relacionit (2.2), çdo fjalë kod i një kodi linear është një kombinim linear i rreshtave të matricës gjeneruese G të kodit. Në këtë rast, padyshim, çdo rresht i matricës G korrespondon me një fjalë kodi. Prandaj, relacioni (2.10) mund të rishkruhet si më poshtë:

Prodhimi i matricave G të madhësisë te* nëse H t madhësia l x (PC)është matrica e madhësisë për të x (l - për), i përbërë nga zero elementë.

Matricë N madhësia ( n-k) x l, vijat e së cilës janë vektorët bazë të komplementit ortogonal të nënhapësirës së kodit linear, quhet matrica e kontrollit kod linear.

Sipas relacionit (2.4), matrica gjeneruese e kodit sistematik linear përbëhet nga matrica e identitetit të rendit për të dhe matricat e simboleve të kontrollit të madhësisë për të x (l - për), e cila, nga ana tjetër, është një zgjatim i matricës së identitetit. Siç tregohet në Shtojcën 1, shumëzimi i dy matricave mund të kryhet duke pjesëtuar matricat që do të shumëzohen me matricat më të vogla(blloqe) me shumëzim pasues të blloqeve individuale të matricave të shumëzuara. Pastaj për matricat G dhe N ti mund te shkruash:

Numri i kolonave në blloqe A dhe B matricat N 7 duhet të përputhet me numrin e rreshtave në blloqe Ek dhe R matricat G (sipas rregullave të shumëzimit të matricës). Matrica që rezulton duhet të ketë madhësi / s * (l - te). Natyrisht, nëse vendosim A = -R dhe V= El_ / s, pastaj matrica N do të plotësojë ekuacionin (2.11).

Pra matrica H tështë një zgjatim i matricës -R dhe përveç matricës - R matricë N përmban matricën e identitetit të rendit P - për të. Matricë H tështë rezultat i transpozimit të matricës N.

Rezultati i transpozimit të përsëritur të matricës është matrica origjinale. Prandaj matrica N mund të merret duke transpozuar matricën N t. Meqenëse për çdo element a, fushat GF [ 2) a = - a është e vërtetë, atëherë për një kod linear binar është e vërtetë R - R.

Matricë N Kodi i linjës binar do të duket kështu:

Matricë R, e përfshirë në matricën G dhe që përmban simbole kontrolli, mund të merret duke transpozuar matricën P t, të përfshira në matricë N.

Kështu, ndërtimi i një kodi linear reduktohet në gjetjen e matricës N. Për një matricë të caktuar Nështë e lehtë të gjesh matricën G.

Shembulli 2.1.4. Merrni parasysh ndërtimin e një kodi linear binar - një kod mbi GF (2) që korrigjon një gabim të një fjale kodi me një sekuencë informacioni të madhësisë për të= 3 bit.

Sipas relacionit (2.9), për një kod me distancë maksimale r = 2-t == 2. Atëherë n = fc + r = 3 + 2 = 5. Megjithatë, siç do të tregohet në nënparagrafin vijues, një kod linear binar (5,3) nuk është i aftë të korrigjojë një gabim të vetëm të fjalës së koduar. Në këtë rast, numri minimal i simboleve të tepërta për këtë rast është G= 3, dhe kodi në shqyrtim është një kod binar linear (6,3).

Kështu, në në këtë rast matricë N përmban një matricë kontrolli të madhësisë / cx (n- / c) = 3 * 3 dhe një matricë identiteti të rendit n-k = 3.

Të gjitha kolonat e matricës N duhet të formojnë grupe të pavarura lineare me dy kolona dhe grupe të varura linearisht prej tre kolonash. Ky kusht plotësohet, për shembull, nga sekuencat 101, 110 dhe 011 mbi GF (2). Sekuencat e specifikuara formojnë kolonat e matricës P t, të përfshira në matricë N. Pjesa tjetër e elementeve të matricës N korrespondojnë me matricën e identitetit të rendit 3:

Duke i shtuar matricës së identitetit të rendit 3, matricën P fitohet duke transpozuar matricën P t, marrim matricën G:

Le të shqyrtojmë tani procesin e formimit dhe strukturën e një fjale kodi të një kodi binar linear (6, 3) me një matricë gjeneruese të formës (2.12):

Tre karakteret e para të fjalës kodike (ci - Cs) përmbajnë simbole informacioni (/ 1 - g "s), të formuara si rezultat i shumëzimit të matricës së sekuencës së informacionit i në matricën e identitetit të rendit 3, e cila është pjesë e matricës G. Simbolet e mbetura të fjalës së koduar (C4 - Cb) përmbajnë simbole kontrolli (t ^ - tz), të marra si rezultat i shumëzimit të matricës së sekuencës së informacionit me matricën e simboleve të kontrollit R, përfshirë gjithashtu në matricën G.

Është e lehtë të kontrollohet se në rastin e kodit (6, 3) - nga Shembulli 2.1.4, numri minimal i simboleve jozero midis të gjitha fjalëve të koduara është tre (fjalë e koduar 001101, 010011,100110 dhe 111000). Në këtë mënyrë, d *= 3 dhe, sipas relacionit (2.5), kodi duhet të korrigjojë një gabim të kodit. Siç do të tregohet në nënparagrafin tjetër, ky është me të vërtetë rasti.