Distribuerad källkodning

Distribuerad källkodning ( DSC ) är ett viktigt problem inom informationsteori och kommunikation . DSC-problem gäller komprimering av flera korrelerade informationskällor som inte kommunicerar med varandra. Genom att modellera korrelationen mellan flera källor på avkodarsidan tillsammans med kanalkoder kan DSC skifta beräkningskomplexiteten från kodarsidan till avkodarsidan och tillhandahåller därför lämpliga ramverk för applikationer med komplexitetsbegränsad sändare, såsom sensornätverk och video/ multimediakomprimering (se distribuerad videokodning). En av huvudegenskaperna hos distribuerad källkodning är att beräkningsbördan i kodare flyttas till den gemensamma avkodaren.

Historia

1973 föreslog David Slepian och Jack Keil Wolf den informationsteoretiska förlustfri komprimering bunden till distribuerad komprimering av två korrelerade iid -källor X och Y. Därefter utvidgades denna gräns till fall med mer än två källor av Thomas M. Cover 1975, medan de teoretiska resultaten i fallet med förlustkompression presenteras av Aaron D. Wyner och Jacob Ziv 1976.

Även om satserna om DSC föreslogs på 1970-talet, var det efter cirka 30 år som försök startade för praktiska tekniker, baserat på idén att DSC är nära besläktad med kanalkodning som föreslogs 1974 av Aaron D. Wyner . Det asymmetriska DSC-problemet togs upp av SS Pradhan och K. Ramchandran 1999, som fokuserade på statistiskt beroende binära och Gaussiska källor och använde skalära och trellis- coset -konstruktioner för att lösa problemet. De utökade arbetet ytterligare till det symmetriska DSC-fallet.

Syndromavkodningsteknologi användes först i distribuerad källkodning av DISCUS -systemet av SS Pradhan och K Ramachandran (Distribuerad källkodning med syndrom). De komprimerar binära blockdata från en källa till syndrom och överför data från den andra källan okomprimerad som sidoinformation. Denna typ av DSC-schema uppnår asymmetriska komprimeringshastigheter per källa och resulterar i asymmetrisk DSC. Detta asymmetriska DSC-schema kan enkelt utvidgas till fallet med mer än två korrelerade informationskällor. Det finns också några DSC-scheman som använder paritetsbitar snarare än syndrombitar.

Korrelationen mellan två källor i DSC har modellerats som en virtuell kanal som vanligtvis kallas en binär symmetrisk kanal .

Från och med DISCUS har DSC lockat till sig betydande forskningsaktivitet och mer sofistikerade kanalkodningstekniker har antagits i DSC-ramverk, såsom Turbo Code , LDPC Code, och så vidare.

I likhet med det tidigare förlustfria kodningsramverket baserat på Slepian-Wolf-satsen, har försök gjorts på förlustfall baserade på Wyner-Ziv-satsen. Teoretiska resultat på kvantiseringsdesigner tillhandahölls av R. Zamir och S. Shamai, medan olika ramverk har föreslagits baserat på detta resultat, inklusive en kapslad gitterkvantiserare och en trelliskodad kvantiserare.

Dessutom har DSC använts vid videokomprimering för applikationer som kräver lågkomplex videokodning, såsom sensornätverk, multiview-videokameror och så vidare.

Med deterministiska och probabilistiska diskussioner om korrelationsmodellen för två korrelerade informationskällor har DSC-scheman med mer generella komprimerade hastigheter utvecklats. I dessa icke-asymmetriska scheman är båda de två korrelerade källorna komprimerade.

Under ett visst deterministiskt antagande om korrelation mellan informationskällor har ett DSC-ramverk i vilket valfritt antal informationskällor kan komprimeras på ett distribuerat sätt demonstrerats av X. Cao och M. Kuijper. Den här metoden utför icke-asymmetrisk komprimering med flexibla hastigheter för varje källa, vilket uppnår samma totala komprimeringshastighet som att upprepade gånger tillämpa asymmetrisk DSC för mer än två källor. Sedan, genom att undersöka den unika kopplingen mellan syndrom och komplementära kodord för linjära koder, har de översatt de viktigaste stegen i DSC gemensam avkodning till syndromavkodning följt av kanalkodning via en linjär blockkod och även via dess komplementkod, som teoretiskt illustrerat en metod av sammansättning av en DSC-fogavkodare från linjära kodkodare och avkodare.

Teoretiska gränser

Den informationsteoretiska förlustfria komprimeringen bunden på DSC ( Slepian–Wolf bound ) var först avsedd av David Slepian och Jack Keil Wolf i termer av entropier av korrelerade informationskällor 1973. De visade också att två isolerade källor kan komprimera data lika effektivt som om de kommunicerade med varandra. Denna gräns har utvidgats till fallet med mer än två korrelerade källor av Thomas M. Cover 1975.

Liknande resultat erhölls 1976 av Aaron D. Wyner och Jacob Ziv med avseende på förlustkodning av gemensamma Gaussiska källor.

Slepian–Wolf bunden

Distribuerad kodning är kodningen av två eller flera beroende källor med separata kodare och gemensam avkodare. Med tanke på två statistiskt beroende iid finita alfabetiska slumpmässiga sekvenser X och Y, inkluderar Slepian–Wolfs sats teoretiska gränser för den förlustfria kodningshastigheten för distribuerad kodning av de två källorna enligt nedan:

$R_{X}\geq H(X|Y),\,$

${\displaystyle R_{Y}\geq H( Y|X),\$

$R_{X}+R_{Y}\geq H(X,Y).\,$

Om både kodaren och avkodaren för de två källorna är oberoende, är den lägsta hastigheten vi kan uppnå för förlustfri komprimering $H(X)$ och $H(Y)$ för $X$ respektive $Y$ , där $H(X)$ och $H(Y)$ är entropierna för $X$ och $Y$ . Men med gemensam avkodning, om sannolikhet för försvinnande fel för långa sekvenser accepteras, visar Slepian–Wolf-satsen att mycket bättre kompressionshastighet kan uppnås. Så länge som den totala hastigheten för $X$ och $Y$ är större än deras gemensamma entropi $H(X,Y)$ och ingen av källorna är kodad med en hastighet som är större än dess entropi, distribuerad kodning kan uppnå godtyckligt liten felsannolikhet för långa sekvenser.

Ett specialfall av distribuerad kodning är komprimering med sidoinformation från dekodern, där källa $Y$ är tillgänglig på avkodarsidan men inte tillgänglig på kodarsidan. Detta kan behandlas som villkoret att $R_{Y}=H(Y)$ redan har använts för att koda $Y$ , medan vi avser att använda $H(X|Y)$ för att koda $X$ . Hela systemet fungerar på ett asymmetriskt sätt (komprimeringshastigheten för de två källorna är asymmetrisk).

Wyner-Ziv bunden

Strax efter att Slepian–Wolfs teorem om förlustfri distribuerad komprimering publicerades, föreslogs utvidgningen till förlustkomprimering med sidoinformation från dekoder som Wyner–Ziv-satsen. På samma sätt som förlustfritt fall ges två statistiskt beroende iid-källor $X$ och ${\displaystyle Y} , där$$Y$ är tillgänglig på avkodarsidan men inte tillgänglig på kodarsidan. Istället för förlustfri komprimering i Slepian-Wolf-satsen undersökte Wyner-Ziv-satsen det förlustfria kompressionsfallet.

Wyner–Ziv-satsen presenterar den uppnåbara nedre gränsen för bithastigheten för $X$ vid given distorsion $D$ . Det visade sig att för Gaussiska minneslösa källor och medelkvadratfelsdistorsion förblir den nedre gränsen för bithastigheten för $X$ densamma oavsett om sidoinformation är tillgänglig vid kodaren eller inte.

Virtuell kanal

Deterministisk modell

Probabilistisk modell

Asymmetrisk DSC vs. symmetrisk DSC

Asymmetrisk DSC betyder att olika bithastigheter används för att koda ingångskällorna, medan samma bithastighet används i symmetrisk DSC. Med en DSC-design med två källor till exempel, i det här exemplet $X$ och $Y$ två diskreta, minneslösa, likformigt fördelade källor som genererar en uppsättning variabler $\mathbf {x}$ och $\mathbf {y}$ med längden 7 bitar och Hamming-avståndet mellan $\mathbf {x}$ och $\mathbf {y}$ är högst ett. Slepian-Wolf på väg till dem är:

$R_{X}+R_{Y}\geq 10$

$R_{X}\geq 5$

$R_{Y}\ geq 5$

Detta betyder att den teoretiska gränsen är $R_{X}+R_{Y}=10$ och symmetrisk DSC betyder 5 bitar för varje källa. Andra par med $R_{X}+R_{Y}=10$ är asymmetriska fall med olika bithastighetsfördelningar mellan $X$ och $Y$ , där $R_{X}=3$ , $R_{Y}=7$ och $R_{Y}=3$ , ${\ displaystyle R_{X}=7}$ representerar två extremfall som kallas avkodning med sidoinformation.

Praktisk distribuerad källkodning

Slepian–Wolf-kodning – förlustfri distribuerad kodning

Man förstod att Slepian–Wolf-kodning är nära besläktad med kanalkodning 1974, och efter cirka 30 år började praktisk DSC implementeras av olika kanalkoder. Motivationen bakom användningen av kanalkoder är från två källors fall, korrelationen mellan ingångskällor kan modelleras som en virtuell kanal som har ingång som källa $X$ och utgång som källa $Y$ . DISCUS -systemet som föreslogs av SS Pradhan och K. Ramchandran 1999 implementerade DSC med syndromavkodning, som fungerade för asymmetriska fall och utökades ytterligare till symmetriska fall .

Det grundläggande ramverket för syndrombaserad DSC är att, för varje källa, dess ingångsutrymme är uppdelat i flera coset enligt den speciella kanalkodningsmetod som används. Varje ingång från varje källa får en utgång som indikerar vilken coset ingången tillhör, och den gemensamma avkodaren kan avkoda alla ingångar genom mottagna coset-index och beroende mellan källor. Utformningen av kanalkoder bör beakta korrelationen mellan ingångskällor.

En grupp koder kan användas för att generera coset-partitioner, såsom trelliskoder och gitterkoder. Pradhan och Ramchandran designade regler för konstruktion av underkoder för varje källa, och presenterade resultatet av trellis-baserade coset-konstruktioner i DSC, som är baserad på faltningskod och set- partitioneringsregler som i Trellis-modulering , såväl som gitterkodbaserad DSC . Efter detta föreslogs inbäddad spaljékod för asymmetrisk kodning som en förbättring jämfört med deras resultat.

Efter att DISCUS-systemet föreslagits har mer sofistikerade kanalkoder anpassats till DSC-systemet, såsom Turbo Code , LDPC Code och Iterative Channel Code. Kodarna för dessa koder är vanligtvis enkla och lätta att implementera, medan avkodarna har mycket högre beräkningskomplexitet och kan få bra prestanda genom att använda källstatistik. Med sofistikerade kanalkoder som har prestanda som närmar sig kapaciteten hos korrelationskanalen, kan motsvarande DSC-system närma sig Slepian-Wolf bound.

Även om den mesta forskningen fokuserade på DSC med två beroende källor, har Slepian–Wolf-kodning utvidgats till fler än två ingångskällor, och metoder för generering av underkoder från en kanalkod föreslogs av V. Stankovic, AD Liveris, etc. korrelationsmodeller.

Allmän teorem om Slepian–Wolf-kodning med syndrom för två källor

Sats : Vilket par som helst av korrelerade likformigt fördelade källor, ${\displaystyle X,Y\in \left\{0,1\right\}^{n}} ,$ med ${\displaystyle \mathbf {d_{H}} (X,Y)\leq t} ,$ kan komprimeras separat med ett hastighetspar $(R_{1},R_ {2})$ så att $R_{1},R_{2}\geq nk,R_{1}+R_{ 2}\geq 2n-k$ , där $R_{1}$ och $R_{2}$ är heltal, och $k\leq n-\log(\sum _{i=0}^{t}{n \choose i})$ . Detta kan uppnås med en $(n,k,2t+1)$ binär linjär kod.

Bevis : Hamming-gränsen för en $(n,k,2t+1)$ binär linjär kod är ${\displaystyle k\leq n-\log(\sum _{i=0}^{t}{n \choose i})} ,$ och vi har Hamming-kod som uppnår denna gräns, därför har vi en sådan binär linjär kod $\mathbf {C}$ med $k\times n$ generatormatris $\mathbf {G}$ . Därefter kommer vi att visa hur man konstruerar syndromkodning baserat på denna linjära kod.

Låt $R_{1}+R_{2}=2n-k$ och $\mathbf {G_{1}}$ bildas genom att först ta $(n-R_{1})$ rader från $\mathbf {G}$ , medan $\mathbf {G_{2}}$ bildas med de återstående $(n-R_{2})$ rader av $\mathbf {G}$ . $\mathbf {C_{1}}$ och $\mathbf {C_{2}}$ är underkoderna till Hamming-koden som genereras av $\mathbf {G_{1} }$ respektive $\mathbf {G_{2}}$ , med $\mathbf {H_{1}}$ och $\mathbf {H_{2}}$ som deras paritetskontrollmatriser.

För ett par indata $\mathbf {(x,y)}$ , ges kodaren av $\mathbf {s_{1}} =\mathbf { H_{1}} \mathbf {x}$ och $\mathbf {s_{2}} =\mathbf {H_{2}} \mathbf {y}$ . Det betyder att vi kan representera $\mathbf {x}$ och $\mathbf {y}$ som $\mathbf {x=u_{1} G_{1}+c_{s1}}$ , $\mathbf {y=u_{2}G_{2}+c_{s2}}$ , där $\mathbf {c_{s1},c_{s2}}$ är representanterna för cosets av $\mathbf {s1,s2}$ med avseende på $\mathbf {C_{1},C_{2}}$ respektive. Eftersom vi har $\mathbf {y=x+e}$ med $w(\mathbf {e} )\leq t$ . Vi kan få ${\displaystyle \mathbf {x+y=uG+c_{s}=e} } ,$ där $\mathbf {u=\left[u_{1},u_{2}\right]}$ , $\mathbf {c_{s}=c_{s1}+c_{s2 }}$ .

Anta att det finns två olika ingångspar med samma syndrom, det betyder att det finns två olika strängar $\mathbf {u^{1},u^{2}} \in \left\{0,1\right\}^{k}$ , så att $\mathbf {u^{1}G+c_{s}=e}$ och $\mathbf {u^{2}G+c_{s}=e}$ . Vi kommer alltså att ha $\mathbf {(u^{1}-u^{2})G=0}$ . Eftersom minsta Hamming-vikt för koden $\mathbf {C}$ är $2t+1$ , avståndet mellan $\mathbf {u_{1}G}$ och $\mathbf {u_{2}G}$ är $\geq 2t+1$ . Å andra sidan, enligt $w(\mathbf {e} )\leq t$ tillsammans med $\mathbf {u^{1}G +c_{s}=e}$ och ${\displaystyle \mathbf {u^{2}G+c_{s}=e} } ,$ vi kommer att ha $d_{H}(\mathbf {u^{1}G,c_{s}} )\leq t$ och ${\displaystyle d_ {H}(\mathbf {u^{2}G,c_{s}} )\leq t} , vilket$ motsäger $d_{H }(\mathbf {u^{1}G,u^{2}G} )\geq 2t+1$ . Därför kan vi inte ha mer än ett ingångspar med samma syndrom.

Därför kan vi framgångsrikt komprimera de två beroende källorna med konstruerade underkoder från en $(n,k,2t+1)$ binär linjär kod, med hastighetspar $(R_{1},R_{2})$ så att ${\displaystyle R_{1}, R_{2 }\geq nk,R_{1}+R_{2}\geq 2n-k} ,$ där $R_{1}$ och $R_{2}$ är heltal, och $k\leq n-\log(\sum _{i=0}^{t}{n \choose i})$ . Logg anger Logg ₂ .

Slepian–Wolf-kodningsexempel

Ta samma exempel som i den föregående delen Asymmetrisk DSC vs. Symmetrisk DSC , den här delen presenterar motsvarande DSC-scheman med coset-koder och syndrom inklusive asymmetriskt fall och symmetriskt fall. Slepian–Wolf bunden för DSC-design visas i föregående del.

Asymmetriskt hölje

I fallet där $R_{X}=3$ och ${\displaystyle R_{Y}=7} ,$ längden på en indatavariabel $\mathbf {y}$ från källan $Y$ är 7 bitar, därför kan den skickas förlustfritt med 7 bitar oberoende av alla andra bitar. Baserat på kunskapen om att $\mathbf {x}$ och $\mathbf {y}$ har Hamming-avstånd högst ett, för ingång $\mathbf {x}$ från källan ${\ displaystyle X}$ , eftersom mottagaren redan har $\mathbf {y}$ , är de enda möjliga $\mathbf {x}$ de med högst 1 avstånd från $\mathbf {y}$ . Om vi ​​modellerar korrelationen mellan två källor som en virtuell kanal, som har ingång $\mathbf {x}$ och utgång $\mathbf {y}$ , så länge vi får $\mathbf {y}$ , allt vi behöver för att framgångsrikt "avkoda" $\mathbf {x}$ är "paritetsbitar" med speciell felkorrigeringsförmåga, med skillnaden mellan $\mathbf {x}$ och $\mathbf {y}$ som kanalfel. Vi kan också modellera problemet med cosets-partition. Det vill säga, vi vill hitta en kanalkod, som kan dela upp utrymmet för ingången $X$ i flera cosets, där varje coset har ett unikt syndrom associerat med sig. Med en given coset och $\mathbf {y}$ finns det bara en $\mathbf {x}$ som är möjlig att vara indata givet korrelationen mellan två källor.

I det här exemplet kan vi använda den $(7,4,3)$ binära Hamming-koden $\mathbf {C}$ , med paritetskontrollmatrisen $\mathbf {H}$ . För en ingång $\mathbf {x}$ från källa $X$ , endast syndromet som ges av $\mathbf {s} =\mathbf {H} \mathbf {x}$ sänds, vilket är 3 bitar. Med mottagna $\mathbf {y}$ och $\mathbf {s}$ , anta att det finns två ingångar $\mathbf {x_{1}}$ och $\ mathbf {x_{2}}$ med samma syndrom $\mathbf {s}$ . Det betyder ${\displaystyle \mathbf {H} \mathbf {x_{1}} =\mathbf {H} \mathbf {x_{2}} } , vilket$ är $\mathbf {H} (\mathbf {x_{1}} -\mathbf {x_{2}} )=0$ . Eftersom den minsta Hamming-vikten på $(7,4,3)$ Hamming Code är 3, $d_{H}(\mathbf {x_{1}} ,\mathbf {x_{2}} )\geq 3$ . Därför kan ingången $\mathbf {x}$ återställas eftersom $d_{H}(\mathbf {x} ,\mathbf {y} )\leq 1$ .

På liknande sätt kan bitfördelningen med $R_{X}=7$ , $R_{Y}=3$ uppnås genom att vända om rollerna för $X$ och $Y$ .

Symmetriskt fall

I symmetriska fall är det vi vill ha samma bithastighet för de två källorna: 5 bitar vardera med separat kodare och gemensam avkodare. Vi använder fortfarande linjära koder för detta system, som vi använde för asymmetriska fall. Grundidén är liknande, men i det här fallet måste vi göra coset-partition för båda källorna, medan för ett par mottagna syndrom (motsvarar en coset) är endast ett par indatavariabler möjliga givet korrelationen mellan två källor.

Anta att vi har ett par linjär kod $\mathbf {C_{1}}$ och $\mathbf {C_{2}}$ och ett kodare-avkodarpar baserat på linjära koder som kan uppnå symmetrisk kodning. Kodarutgången ges av: $\mathbf {s_{1}} =\mathbf {H_{1}} \mathbf {x}$ och $\ mathbf {s_{2}} =\mathbf {H_{2}} \mathbf {y}$ . Om det finns två par giltiga ingångar $\mathbf {x_{1}} ,\mathbf {y_{1}}$ och $\mathbf {x_{2} } ,\mathbf {y_{2}}$ genererar samma syndrom, dvs $\mathbf {H_{1}} \mathbf {x_{1}} =\mathbf {H_ {1}} \mathbf {x_{2}}$ och $\mathbf {H_{1}} \mathbf {y_{1}} =\mathbf {H_{1} } \mathbf {y_{2}}$ , vi kan få följande( $w()$ representerar Hamming vikt):

${\displaystyle \mathbf {y_{1}} =\mathbf {x_{1}} +\mathbf {e_{1}} } ,$ där $w(\mathbf {e_{1}} )\leq 1$

${\displaystyle \mathbf {y_{2}} =\mathbf {x_{2}} +\mathbf {e_{2}} } ,$ där $w(\mathbf {e_{2}} )\leq 1$

Alltså: $\mathbf {x_{1}} +\mathbf {x_{2}} \in \mathbf {C_{1}}$

$\mathbf {y_{1}} +\mathbf {y_{2}} =\mathbf {x_{1}} +\mathbf { x_{2}} +\mathbf {e_{3}} \in \mathbf {C_{2}}$

där $\mathbf {e_{3}} =\mathbf {e_{2}} +\mathbf {e_{1}}$ och $w(\mathbf {e_{3}} )\leq 2$ . Det betyder att så länge vi har ett minsta avstånd mellan de två koderna större än $3$ , kan vi uppnå felfri avkodning.

De två koderna $\mathbf {C_{1}}$ och $\mathbf {C_{2}}$ kan konstrueras som underkoder till $( 7,4,3)$ Hamming-kod och har därför ett minsta avstånd på $3$ . Givet generatormatrisen $\mathbf {G}$ för den ursprungliga Hamming-koden, generatormatrisen $\mathbf {G_{1}}$ för $\mathbf {C_{1} }$ konstrueras genom att ta två valfria rader från $\mathbf {G}$ , och $\mathbf {G_{2}}$ konstrueras av de återstående två raderna av $\mathbf {G}$ . Motsvarande $(5\times 7)$ paritetskontrollmatris för varje underkod kan genereras enligt generatormatrisen och användas för att generera syndrombitar.

Wyner-Ziv-kodning – distribuerad kodning med förlust

I allmänhet erhålls ett Wyner-Ziv-kodningsschema genom att lägga till en kvantiserare och en avkvantiserare till Slepian-Wolf-kodningsschemat. Därför kan en Wyner-Ziv-kodardesign fokusera på kvantiseraren och motsvarande rekonstruktionsmetoddesign. Flera kvantiseringsdesigner har föreslagits, såsom en kapslad gitterkvantiserare, trelliskodkvantiserare och Lloyd-kvantiseringsmetod.

Storskalig distribuerad kvantisering

Tyvärr skalas inte ovanstående tillvägagångssätt (i krav på design eller driftskomplexitet) till sensornätverk av stora storlekar, ett scenario där distribuerad komprimering är till stor hjälp. Om det finns N källor som sänder med R bitar vardera (med något distribuerat kodningsschema), skalar antalet möjliga rekonstruktioner $2^{NR}$ . Även för måttliga värden på N och R (säg N=10, R = 2) blir tidigare designscheman opraktiska. Nyligen har ett tillvägagångssätt, med hjälp av idéer lånade från Fusion Coding of Correlated Sources, föreslagits där design och operationell komplexitet växlas mot avkodarprestanda. Detta har möjliggjort distribuerad kvantiseringsdesign för nätverksstorlekar som når 60 källor, med betydande vinster jämfört med traditionella metoder.

Den centrala idén är närvaron av en bitdelmängdsväljare som upprätthåller en viss delmängd av de mottagna (NR-bitarna, i exemplet ovan) för varje källa. Låt ${\mathcal {B}}$ vara mängden av alla delmängder av NR-bitarna, dvs.

${\mathcal {B}}=2^{\{1,...,NR\}}$

Sedan definierar vi bit-delmängdsväljarmappningen att vara

${\mathcal {S}}:\{1,...,N\}\högerpil {\mathcal {B}}$

Notera att varje val av bitdelmängdsväljaren ställer ett lagringskrav (C) som är exponentiellt i kardinaliteten hos uppsättningen av valda bitar.

$C=\sum _{n=1}^{N}2^{|{\mathcal {S}}(n)|}$

Detta möjliggör ett klokt urval av bitar som minimerar distorsionen, med tanke på begränsningarna för dekoderlagring. Ytterligare begränsningar av uppsättningen tillåtna delmängder behövs fortfarande. Den effektiva kostnadsfunktionen som måste minimeras är en viktad summa av distorsion och dekoderlagring

$J=D+\lambda C$

Systemdesignen utförs genom att iterativt (och inkrementellt) optimera kodarna, avkodaren och bitdelmängdsväljaren tills konvergens.

Icke-asymmetrisk DSC för mer än två källor

Syndrommetoden kan fortfarande användas för mer än två källor. Betrakta $a$ binär källa med längd- $n$$\mathbf {x} _{1},\mathbf { x} _{2},\cdots ,\mathbf {x} _{a}\in \{0,1\}^{n}$ . Låt ${\displaystyle \mathbf {H} _{1},\mathbf {H} _{2},\cdots ,\mathbf {H} _{s}} vara$ motsvarande kodningsmatriser av storlekarna $m_{1}\times n,m_{2}\times n,\cdots ,m_{a}\times n$ . Sedan komprimeras de binära ingångskällorna till $\mathbf {s} _{1}=\mathbf {H } _{1}\mathbf {x} _{1},\mathbf {s} _{2}=\mathbf {H} _{2}\mathbf {x} _{2},\cdots ,\mathbf { s} _{a}=\mathbf {H} _{a}\mathbf {x} _{a}$ av totalt $m=m_{1}+m_ {2}+\cdots m_{a}$ bitar. Tydligen kan två källtuplar inte återvinnas samtidigt om de delar samma syndrom. Med andra ord, om alla källtupler av intresse har olika syndrom, kan man återhämta dem förlustfritt.

Allmänt teoretiskt resultat verkar inte finnas. Men för en begränsad typ av källa så kallad Hamming-källa som bara har högst en källa som skiljer sig från resten och högst en bitplats inte alla är identiska, praktisk förlustfri DSC visas i vissa fall. För fallet när det finns fler än två källor, är antalet källtuplar i en Hamming-källa $2^{n}(an+1)$ . Därför måste en packningsgräns som $2^{m}\geq 2^{n}(an+1)$ uppenbarligen uppfylla. När packningsbunden är tillfredsställd med likhet, kan vi kalla en sådan kod för att vara perfekt (en analog till perfekt kod i felkorrigerande kod).

En enklaste uppsättning av $a,n,m$ för att tillfredsställa packningen bunden med likhet är $a=3,n=5,m= 9$ . Det visar sig dock att sådan syndromkod inte existerar. Den enklaste (perfekta) syndromkoden med fler än två källor har $n=21$ och $m=27$ . Låta

${pmatrix}},}$${\displaystyle \mathbf {Q} _{1}={\begin{pmatrix}1\;0\;0\;0\;0\;0\;1\;0\;0\; 0\;0\;1\;1\;1\;0\;1\;1\;0\;0\;0\;0\\0\;1\;0\;0\;0\ ;0\;1\;1\;0\;0\;0\;0\;1\;0\;0\;0\;0\;0\;1\;1\;1\\0 \;0\;1\;0\;0\;0\;0\;1\;1\;0\;0\;0\;0\;1\;1\;1\;0\; 1\;0\;1\;1\\0\;0\;0\;1\;0\;0\;0\;0\;1\;1\;0\;0\;0\ ;1\;0\;0\;1\;1\;1\;1\;0\\0\;0\;0\;0\;1\;0\;0\;0\;0 \;1\;1\;0\;1\;0\;1\;1\;0\;1\;1\;1\;1\\0\;0\;0\;0\; 0\;1\;0\;0\;0\;0\;1\;1\;0\;0\;1\;0\;0\;1\;1\;0\;1\$$} _{2}={\ börja{pmatrix}0\;0\;0\;1\;0\;1\;1\;0\;1\;1\;1\;1\;0\;1\;0\;0 \;0\;1\;1\;1\;1\\1\;0\;0\;0\;1\;0\;1\;1\;0\;1\;1\; 1\;1\;0\;1\;1\;1\;1\;0\;0\;0\\0\;1\;0\;0\;0\;1\;1\ ;1\;1\;0\;1\;1\;1\;0\;0\;0\;0\;0\;1\;0\;1\\1\;0\;1 \;0\;0\;0\;1\;1\;1\;1\;0\;1\;0\;1\;1\;1\;0\;0\;1\; 1\;1\\0\;1\;0\;1\;0\;0\;1\;1\;1\;1\;1\;0\;0\;0\;1\ ;0\;1\;1\;0\;1\;1\\0\;0\;1\;0\;1\;0\;0\;1\;1\;1\;1 \;1\;1\;1\;0\;1\;0\;1\;1\;1\;0\end{pmatrix}},}$$\mathbf {Q} _{3}={\begin{pmatrix}1\;0\;0\;1\;0\; 1\;0\;0\;1\;1\;1\;0\;1\;0\;0\;1\;1\;1\;1\;1\;1\\1\ ;1\;0\;0\;1\;0\;0\;0\;0\;1\;1\;1\;0\;0\;1\;1\;1\;1 \;1\;1\;1\\0\;1\;1\;0\;0\;1\;1\;0\;0\;0\;1\;1\;1\; 1\;1\;1\;0\;1\;1\;1\;0\\1\;0\;1\;1\;0\;0\;1\;1\;0\ ;0\;0\;1\;0\;0\;1\;1\;1\;1\;0\;0\;1\\0\;1\;0\;1\;1 \;0\;1\;1\;1\;0\;0\;0\;1\;0\;0\;1\;1\;0\;1\;0\;0\\ 0\;0\;1\;0\;1\;1\;0\;1\;1\;1\;0\;0\;1\;1\;1\;1\;0\ ;0\;0\;1\;1\end{pmatrix}},$${\displaystyle \mathbf {G} =[\mathbf {0} |\mathbf {I} _{9}]} ,$ och ${\displaystyle \mathbf {G} ={\begin{pmatrix}\mathbf {G} _{1}\\\mathbf {G} _{2}\\\mathbf {G} _{3}\end{pmatrix}}} så$ att $\mathbf {G} _{1},\mathbf {G} _{2},\mathbf {G} _{3}$ är vilken partition som helst av $\mathbf {G }$ .

$\mathbf {H} _{1}={\begin{pmatrix}\mathbf {G} _{1}\\\mathbf {Q} _{1}\end{pmatrix}},\mathbf {H} _{2}={\begin{pmatrix}\mathbf {G} _{2} \\\mathbf {Q} _{2}\end{pmatrix}},\mathbf {H} _{3}={\begin{pmatrix}\mathbf {G} _{3}\\\mathbf {Q} _{3}\end{pmatrix}}$ kan komprimera en Hamming-källa (dvs källor som inte har mer än en bit olika kommer alla att ha olika syndrom). Till exempel, för $\mathbf {H} _{1}={\begin{pmatrix}0\;0\;0\; 0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;1\;0\ ;0\\0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0 \;0\;0\;0\;1\;0\\0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\; 0\;0\;0\;0\;0\;0\;0\;0\;0\;1\\1\;0\;0\;0\;0\;0\;1\ ;0\;0\;0\;0\;1\;1\;1\;0\;1\;1\;0\;0\;0\;0\\0\;1\;0 \;0\;0\;0\;1\;1\;0\;0\;0\;0\;1\;0\;0\;0\;0\;0\;1\; 1\;1\\0\;0\;1\;0\;0\;0\;0\;1\;1\;0\;0\;0\;0\;1\;1\ ;1\;0\;1\;0\;1\;1\\0\;0\;0\;1\;0\;0\;0\;0\;1\;1\;0 \;0\;0\;1\;0\;0\;1\;1\;1\;1\;0\\0\;0\;0\;0\;1\;0\; 0\;0\;0\;1\;1\;0\;1\;0\;1\;1\;0\;1\;1\;1\;1\\0\;0\ ;0\;0\;0\;1\;0\;0\;0\;0\;1\;1\;0\;0\;1\;0\;0\;1\;1 \;0\;1\end{pmatrix}},$ en möjlig uppsättning kodningsmatriser ${\displaystyle$$\mathbf {H} _{3}={\begin{pmatrix}0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0 \;0\;1\;0\;0\;0\;0\;0\;0\;0\;0\\0\;0\;0\;0\;0\;0\; 0\;0\;0\;0\;0\;0\;0\;1\;0\;0\;0\;0\;0\;0\;0\\0\;0\ ;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;1\;0\;0\;0\;0 \;0\;0\\1\;0\;0\;1\;0\;1\;0\;0\;1\;1\;1\;0\;1\;0\; 0\;1\;1\;1\;1\;1\;1\\1\;1\;0\;0\;1\;0\;0\;0\;0\;1\ ;1\;1\;0\;0\;1\;1\;1\;1\;1\;1\;1\\0\;1\;1\;0\;0\;1 \;1\;0\;0\;0\;1\;1\;1\;1\;1\;1\;0\;1\;1\;1\;0\\1\; 0\;1\;1\;0\;0\;1\;1\;0\;0\;0\;1\;0\;0\;1\;1\;1\;1\ ;0\;0\;1\\0\;1\;0\;1\;1\;0\;1\;1\;1\;0\;0\;0\;1\;0 \;0\;1\;1\;0\;1\;0\;0\\0\;0\;1\;0\;1\;1\;0\;1\;1\; 1\;0\;0\;1\;1\;1\;1\;0\;0\;0\;1\;1\end{pmatrix}}.$

Se även

• Linjär kod
• Syndromavkodning
• Kod för paritetskontroll med låg densitet
• Turbokod