분산 소스 코딩

정보이론
엔트로피 미분 엔트로피 조건부 엔트로피 관절 엔트로피 상호정보 조건상호정보 상대 엔트로피 엔트로피 레이트 이산형 점의 밀도 제한
점증적 설비 특성 비율-분산 이론
섀넌의 소스 코딩 정리 채널 용량 노이즈 채널 코딩 정리 섀넌-하틀리 정리
v t

DSC(Distributed Source Coding)는 정보이론과 통신에서 중요한 문제다.DSC 문제는 서로 통신하지 않는 복수의 상관관계가 있는 정보원의 압축을 고려한다.^[1]DSC는 채널 코드와 함께 디코더 측의 여러 소스 간의 상관관계를 모델링함으로써 계산 복잡성을 인코더 측에서 디코더 쪽으로 전환할 수 있으므로 센서 네트워크와 비디오/멀티미디어 압축과 같이 복잡성이 제한된 송신기가 있는 애플리케이션에 적합한 프레임워크를 제공할 수 있다(distance 참조).늑골 비디오 부호화^[2]).분산 소스 코딩의 주요 특성 중 하나는 인코더의 계산 부담이 공동 디코더로 이동한다는 것이다.

역사

1973년에 David Slepian과 Jack Keil Wolf는 두 개의 상관관계가 있는 I.i.d. 출처 X와 Y의 분산 압축에 대한 정보 이론적 무손실 압축을 제안했다.^[3]그 후, 이 구속은 토마스 M에 의해 세 가지 이상의 출처가 있는 사례로 확대되었다. 손실 압축 케이스에 대한 이론적 결과는 Aaron D에 의해 제시되는 동안 1975년에 다루어라.[4] 1976년 와이너와 제이콥 지브.^[5]

1970년대 DSC에 대한 이론이 제시됐지만 1974년 아론 D가 제안한 채널 코딩과 밀접한 관련이 있다는 점에 착안해 실용적 기법을 위한 시도가 시작된 것은 약 30년 만이다. 와이너.^[6] 비대칭 DSC 문제는 S. S. 프라단과 K가 해결했다.1999년 람찬드란은 통계적으로 의존하는 이항과 가우스 선원에 초점을 맞추고 문제를 해결하기 위해 스칼라와 트렐리스 코제트 구조를 사용했다.^[7]그들은 그 일을 더 나아가 대칭 DSC 사건으로 확대했다.^[8]

신드롬 디코딩 기술은 SS 프라단과 K 라마찬드란(신드롬을 이용한 분산 소스 코딩)의 DISCUS 시스템에 의해 분산 소스 코딩에 처음 사용되었다.^[7]그들은 한 소스의 이진 블록 데이터를 신드롬으로 압축하고 압축되지 않은 다른 소스의 데이터를 측면 정보로 전송한다.이러한 종류의 DSC 계획은 소스당 비대칭 압축률을 달성하고 비대칭 DSC를 초래한다.이 비대칭 DSC 체계는 세 개 이상의 상관관계가 있는 정보 출처의 경우에 쉽게 확장될 수 있다.신드롬 비트 대신 패리티 비트를 사용하는 DSC 방식도 있다.

DSC에서 두 소스 간의 상관관계는 일반적으로 이진 대칭 채널이라고 하는 가상 채널로 모델링되었다.^[9][10]

DISCUS를 시작으로 DSC는 유의미한 연구 활동을 유치하였으며, 터보 코드, LDPC 코드 등 보다 정교한 채널 코딩 기법이 DSC 프레임워크에 채택되었다.

Slepian-based에 기초한 이전의 무손실 코딩 프레임워크와 유사하다.Wolf 정리, Wyner-Ziv 정리에 근거한 손실 사례에 대한 노력이 이루어졌다.정량자 설계에 대한 이론적 결과는 R. Zamir와 S에 의해 제공되었다.샤마이(^[11]Shamai)는 중첩 격자 정량기(Named Lattice quantizer)와 트레일리스 코드 정량기(Trellis-coded quantizer)를 포함하여 이 결과에 따라 다른 프레임워크가 제안되었다

또한, DSC는 센서 네트워크, 멀티뷰 비디오 캠코더 등과 같이 낮은 복잡도의 비디오 인코딩이 필요한 어플리케이션의 비디오 압축에 사용되어 왔다.^[12]

상관관계가 있는 두 정보원의 상관관계 모델에 대한 결정론적, 확률론적 논의와 함께, 보다 일반적인 압축률을 가진 DSC 체계가 개발되었다.^[13][14][15]이러한 비대칭 체계에서는 상관관계가 있는 두 선원이 모두 압축된다.

정보 출처 간의 상관관계에 대한 특정한 결정론적 가정 하에서, 임의의 수의 정보 출처를 분산 방식으로 압축할 수 있는 DSC 프레임워크는 X에 의해 입증되었다.조와 M.쿠이퍼.^[16]이 방법은 각 소스에 대해 유연한 속도로 비대칭 압축을 수행하여 세 개 이상의 소스에 대해 비대칭 DSC를 반복적으로 적용하는 것과 동일한 전체 압축률을 달성한다.그리고 나서, 증후군, 직선 코드의 보완 codewords 사이의 독특한 연결 조사하여 그들은 국군 기무 사령부 합동 디코딩의 증후군 해독에 주요 단계 채널 선형 블록 코오드고는 이론적으로 국군 기무 사령부 합동 de를 구성하는 방법을 설명하는 보충 code,[17]또한을 통해 인코딩에 이어번역해 두었습니다.대구선형 코드 인코더 및 디코더에서 er.

이론적 한계

DSC에 바인딩된 정보 이론적 무손실 압축(Slepian–)Wolf bound)는 1973년 관련 정보 출처의 엔트로피 측면에서 David Slepian과 Jack Keil Wolf에 의해 처음 고안되었다.^[3]그들은 또한 두 개의 분리된 출처가 서로 의사소통하는 것처럼 데이터를 효율적으로 압축할 수 있다는 것을 보여주었다.이 경계는 토마스 M에 의해 두 개 이상의 상관관계가 있는 출처의 사례로 확대되었다. 1975년 커버.^[4]

비슷한 결과가 1976년에 Aaron D에 의해 얻어졌다. 와이너와 제이콥 지브는 가우스 공동 출처의 손실 코딩에 관하여.^[5]

슬레피안-울프 바운드

분산 코딩(Distributed Coding)은 별도의 인코더와 공동 디코더를 사용하여 둘 이상의 종속 선원을 코드화하는 것이다.통계적으로 의존하는 2개의 유한 알파벳 랜덤 시퀀스 X와 Y를 주어진다면 슬레피안–Wolf 정리에는 다음과 같은 두 선원의 분산 코딩에 대한 무손실 코딩 비율에 대한 이론적 결합이 포함된다.^[3]

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

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

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

If both the encoder and decoder of the two sources are independent, the lowest rate we can achieve for lossless compression is ${\displaystyle H(X)}$ and ${\displaystyle H(Y)}$ for ${\displaystyle X}$ and ${\displaystyle Y}$ respectively, where ${\displaystyle H(X)}$ and ${\disp$$레이스타일 H(Y)}$는 $X{\displaystyle }$ ${\displaystyle$ X$}$과 $Y{\displaystyle }$ ${\displaystyle Y}$의 엔트로피지만$,$ 공동 디코딩으로 긴 시퀀스에 대한 소멸 오차 확률을 허용하면 슬레피안–늑대 정리는 훨씬 더 나은 압축률을 달성할 수 있다는 것을 보여준다.$X{\displaystyle }$ ${\displaystyle X}$ 및 $Y$ ${\displaystyle Y}$의 총 비율이 공동$$ 엔트로피 $H{\displaystyle (X,}$ ${\displaystyle Y)}$ ${\displaystyle H(X,Y)}$보다 크고 어떤$$ 소스도 엔트로피보다 큰 비율로 인코딩되지 않는 한 분산 코딩은 긴 시퀀스에 대해 임의로 작은 오류 확률을 달성할 수 있다.

분산 코딩의 특별한 경우는 디코더 측 정보가 포함된 압축으로, 여기서 소스 $Y{\displaystyle }$ ${\displaystyle Y}$은(는) 디코더 측에서는 사용할 수 있지만$$ 인코더 측에서는 액세스할 수 없다.$이것$은 $우리$가 $H{\displaystyle }$${\displaystyle }$( ${\displaystyle X}$ ${\displaystyle Y}$) {\$displaystyle$ $Y}$을(를) 인코딩하기 위해$$ H ( X Y) ${\displaystyle H(X$$$Y$)}$을(를) 사용하는 동안$,$ R${\displaystyle {}_{}{Y}_{}}$ = $H$displaystystyle Y$} {\displaysty$X}를 인코딩하는 데 이미 사용되었다는$$ 조건으로 취급할 수 있다$.$전체 시스템이 비대칭적으로 작동하고 있다(두 선원에 대한 압축률은 비대칭이다).

와이너-지브 바운드

슬레피안-후 얼마 지나지 않아무손실 분산압축에 대한 Wolf 정리가 발표되었고, 디코더 측정보로 손실압축에 대한 확장이 Wyner-Ziv 정리로서 제안되었다.^[5]무손실 사례와 유사하게, 두 개의 통계적으로 의존하는 I.i.d. $source$$$X {\$displaystyle$ X$}$ 및$Y{\displaystyle }$ {\$displaystyle$ Y$}$이(가$$) 제공되며, $여기$서$$Y {\\$displaystyle$ Y}은 디코더 쪽에서는$$ 사용할 수 있지만 인코더 쪽에서는 액세스할 수 없다.슬레피안에서는 무손실 압축 대신울프 정리, 와이너-지브 정리는 손실 압축 케이스를 들여다보았다.

Wyner-Ziv 정리는 $주어진{\displaystyle }$ 왜곡 $D{\displaystyle }$ ${\displaystyle D}$에서 X ${\displaystyle X}$의 비트 전송률에 대해 달성 가능한 하한을 제시한다$.$ 가우스 메모리 소스와 평균 제곱 오차 왜곡의 경우, $X{\displaystyle }$ ${\displaystyle X}$의 비트 전송률에 대한 하한을 측면의 정보와는 상관없이 동일하게 유지하는$$ 것으로 확인되었다.인코더에서 tion을 사용할 수 있는지 여부.

가상 채널

결정론적 모형

확률론적 모형

비대칭 DSC 대 대칭 DSC

비대칭 DSC는 입력 소스를 코딩할 때 서로 다른 비트 전송률이 사용되는 반면 대칭 DSC에서는 동일한 비트 전송률이 사용되는 것을 의미한다.예를 들어, 이 $예제$에서 X$${\$displaystyle$X} 및$$ $Y{\displaystyle }${\$displaystyle Y}$은(는) $변수{\displaystyle \mathbf{}}$ x$${\$displaystyle \mathbf$ ${$$x}$ $및$ y ${\$ {$y}$의 길이 7비트와 해밍 거리 베트의 두 개의 소스를 생성하는 이산형 메모리 없는 균일하게 분포된 소스입니다$$.ween $x{\displaystyle \mathbf{}}$ ${\$및$$ $y{\displaystyle \mathbf{}}$ ${\$은(는) 최대$$ 하나.슬레피안-늑대가 그들에게 매여 있는 것은 다음과 같다.

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

${\displaystyle R_{X}\geq 5}$

${\displaystyle R_{Y}\geq 5}$

즉, 이론적 바운드는 R ${\displaystyle X_{}}$+ ${\displaystyle R_{}}$Y = ${\displaystyle 10}$ ${\displaystyle R_{X}+R_{{}}{$$Y}=10}$ 및$$ 대칭 DSC는 각 소스에 대해 5비트를 의미한다.$R{\displaystyle {}_{}}$ ${\displaystyle X_{}}$+ ${\displaystyle {}_{}}$ ${\displaystyle Y_{}}$= ${\displaystyle 10}$ ${\displaystyle R_{X}+R_{{}$가 있는 다른 쌍$Y}=10}$은(는) $X{\displaystyle }$ ${\displaystyle X}$과(와) $Y{\displaystyle }$ ${\displaystyle Y}$ 사이에 비트율 분포가 서로 다른 비대칭 사례로$,$ $여기$서 ${\displaystyle R_{}}$X = ${\displaystyle 3}${\$displaystyle R_{X}=3$ $R{\displaystyle {}_{}{Y}_{}}$ = ${\displaystyle 7}${\$displaystystyle R_{{{{{}}.$${\displaystyle \mathrm{Y}}$$}=7}$ 및$$ ${\displaystyle R_{}}$ Y${\displaystyle {}_{}}$= 3 ${\displaystyle R_{$${\displaystyle \mathrm{Y}}$$}=3}$, $R{\displaystyle {}_{}}$ ${\displaystyle X_{}}$= 7 ${\displaystyle R_{X}=7}$은 측면 정보로 해독하는 두 가지 극단적인 경우를 나타낸다.

실제 분산 소스 코딩

슬레피안-Wolf 부호화 – 무손실 분산 부호화

슬레피안-로 이해됐다.울프 코딩은 1974년 채널 코딩과 밀접한 관련이 있으며,^[6] 약 30년 후부터는 서로 다른 채널 코드에 의해 실용 DSC가 구현되기 시작했다.채널 코드를 사용하는 동기는 두 가지 소스 사례에서 비롯된다. 입력 소스 간의 상관관계는 소스 $X{\displaystyle }$ ${\displaystyle$ X$}$로 입력을 하고 $소스{\displaystyle }$ Y ${\displaystyle Y}$로 출력을 갖는 가상 채널로 모델링할 수 있다$.$ S. S. Pradhan과 K가 제안한 DISCUS 시스템.램찬드란은 1999년 신드롬 디코딩을 가진 DSC를 구현해 비대칭 케이스에 효과가 있었고 대칭 케이스까지 확대됐다.^[7][8]

신드롬 기반 DSC의 기본 골격은 각 출처에 대해 그 입력 공간을 사용하는 특정 채널 코딩 방법에 따라 여러 코세트로 분할하는 것이다.각 소스의 모든 입력은 입력이 속하는 코제트를 나타내는 출력을 얻으며, 공동 디코더는 받은 코제트 지수와 소스 간의 의존성에 의해 모든 입력을 디코딩할 수 있다.채널 코드의 설계에서는 입력 소스 간의 상관 관계를 고려해야 한다.

trellis 코드와 격자 코드와 같은 ^[18]코셋 파티션을 생성하기 위해 코드 그룹을 사용할 수 있다.프라단과 람찬드란은 각 소스의 서브코드 구축을 위한 규칙을 설계하였고, 트레일리스 변조에서와 같이 콘볼루션 코드와 설정 파티셔닝 규칙에 근거한 DSC의 트레일리스 기반 코스메트 시공 결과, 격자 코드 기반 DSC를 제시했다.^[7][8]그 후, 비대칭 코딩에 대한 임베디드 트렐리스 코드는 그 결과에 대한 개선으로서 제안되었다.^[19]

DISCUS 시스템이 제안된 후, 터보 코드, LDPC 코드, 반복 채널 코드 등 보다 정교한 채널 코드가 DSC 시스템에 적용되었다.이들 코드의 인코더는 보통 간단하고 구현이 용이한 반면 디코더는 계산 복잡성이 훨씬 높고 소스 통계를 활용해 좋은 성능을 얻을 수 있다.성능은 상관 채널 용량에 근접하는 정교한 채널 코드로 해당 DSC 시스템은 슬레피언-로 접근할 수 있다.울프 바운드

비록 대부분의 연구가 두 개의 종속된 출처를 가진 DSC에 초점을 맞췄지만, 슬레피언은-울프 코딩은 3개 이상의 입력 소스 케이스로 확장되었으며, V는 하나의 채널 코드의 서브 코드 생성 방법을 제안하였다.스탄코비치, A. D. 리버니스 등은 특정한 상관관계 모델을 부여했다.^[20]

슬레피안의 총정리두 가지 소스용 신드롬으로 늑대 부호화

정리:Any pair of correlated uniformly distributed sources, ${\displaystyle X,Y\in \left\{0,1\right\}^{n}}$, with ${\displaystyle \mathbf {d_{H}} (X,Y)\leq t}$, can be compressed separately at a rate pair ${\displaystyle (R_{1},R_{2})}$ such that ${\displaystyle R_1,R_{}}$${\displaystyle R_{1},R_{2}\geq n-k,R_{1}+R_{2}\geq 2n-k}$, where ${\displaystyle R_{1}}$ and ${\displaystyle R_{2}}$ are integers, and ${\displaystyle k\leq n-\log(\sum _{i=0}^{t}{n \choose i})}$.이는${\displaystyle }$(${\displaystyle n}$, ${\displaystyle k}$, ${\displaystyle 2}$ ${\displaystyle \mathrm{t}}$+ 1${\displaystyle }$) ${\displaystyle (n,k,2t+1)}$ 이진$$ 선형 코드를 사용하여 달성할 수 있다.

Proof: The Hamming bound for an ${\displaystyle (n,k,2t+1)}$ binary linear code is ${\displaystyle k\leq n-\log(\sum _{i=0}^{t}{n \choose i})}$, and we have Hamming code achieving this bound, therefore we have such a binary linear code ${\displaystyle \math$$bf$$${C$}$ ${\displaystyle k}$ n {\$displaystyle$ k\$times n}$ $생성기{\displaystyle \mathbf{}}$매트릭스 G {\$displaystyle$\mathbf {$G}$$}.$ 다음은 이 선형 코드를 기반으로 신드롬 인코딩을 구성하는 방법을 보여 준다.

Let ${\displaystyle R_{1}+R_{2}=2n-k}$ and ${\displaystyle \mathbf {G_{1}} }$ be formed by taking first ${\displaystyle (n-R_{1})}$ rows from ${\displaystyle \mathbf {G} }$, while ${\displaystyle \mathbf {G_{2}} }$ is formed using the remaining ${\displaystyle (n}$${\displaystyle (n-R_{2})}$ rows of ${\displaystyle \mathbf {G} }$. ${\displaystyle \mathbf {C_{1}} }$ and ${\displaystyle \mathbf {C_{2}} }$ are the subcodes of the Hamming code generated by ${\displaystyle \mathbf {G_{1}} }$ and ${\displaystyle \mathbf {G_{2}}$$}}$은(는$$) ${\displaystyle {각각\mathbf{}}_{}}$H 1 {\$displaystyle$ \$mathbf$ {$H_{$1}$}$과($)$ H 2 {\$displaystyle$ \$mathbf {H_2}} }$을(를) 패리티 검사 매트릭스로 사용한다$$.

For a pair of input ${\displaystyle \mathbf {(x,y)} }$, the encoder is given by ${\displaystyle \mathbf {s_{1}} =\mathbf {H_{1}} \mathbf {x} }$ and ${\displaystyle \mathbf {s_{2}} =\mathbf {H_{2}} \mathbf {y} }$. That means, we can represent ${\displaystyle \$$mathbf {x} }$ and ${\displaystyle \mathbf {y} }$ as ${\displaystyle \mathbf {x=u_{1}G_{1}+c_{s1}} }$, ${\displaystyle \mathbf {y=u_{2}G_{2}+c_{s2}} }$, where ${\displaystyle \mathbf {c_{s1},c_{s2}} }$ are the representatives of t각각$$$$ $C{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {1\mathbf{}}_{}}$,${\displaystyle {}_{}\mathbf{}{\mathbf{}}_{}}$ 2 ${\$ C ${\displaystyle {2\mathbf{}}_{}}$ ${\$}} $}$의 코스셋.Since we have ${\displaystyle \mathbf {y=x+e} }$ with ${\displaystyle w(\mathbf {e} )\leq t}$. We can get ${\displaystyle \mathbf {x+y=uG+c_{s}=e} }$, where ${\displaystyle \mathbf {u=\left[u_{1},u_{2}\right]} }$, ${\displaystyle {\mathbf{c}}_{\mathbf{s}}\mathbf{=}{\mathbf{c}}_{\mathbf{s}\mathbf{1}}}$${\displaystyle \mathbf{+}}$ ${\displaystyle {\mathbf{}}_{}}$ s ${\displaystyle {\mathbf{2}}_{}}$ ${\$$}$ .

Suppose there are two different input pairs with the same syndromes, that means there are two different strings ${\displaystyle \mathbf {u^{1},u^{2}} \in \left\{0,1\right\}^{k}}$, such that ${\displaystyle \mathbf {u^{1}G+c_{s}=e} }$ and ${\displaystyle {\mathbf{u}}^{\mathbf{2}}\mathbf{G}\mathbf{+}{\mathbf{c}}_{\mathbf{s}}\mathbf{=}\mathbf{e}}$${\displaystyle \mathbf {u^{2}G+c_{s}=e$ ${\displaystyle \mathbf{따라서}}{\displaystyle \mathbf{}}$(${\displaystyle {u\mathbf{}}^{}\mathbf{}}$1 - ${\displaystyle {u\mathbf{}}^{}\mathbf{}}$2 )${\displaystyle \mathbf{}}$G = ${\displaystyle \mathbf{0}}${\$displaystyle \mathbf {(u^{1}-u^{2})$가 될 것이다.$G=0} }$. Because minimum Hamming weight of the code ${\displaystyle \mathbf {C} }$ is ${\displaystyle 2t+1}$, the distance between ${\displaystyle \mathbf {u_{1}G} }$ and ${\displaystyle \mathbf {u_{2}G} }$ is ${\displaystyle \geq 2t+1}$.On the other hand, according to ${\displaystyle w(\mathbf {e} )\leq t}$ together with ${\displaystyle \mathbf {u^{1}G+c_{s}=e} }$ and ${\displaystyle \mathbf {u^{2}G+c_{s}=e} }$, we will have ${\displaystyle d_{H}(\mathbf$${u^{1}G,c_{s}} )\leq t}$ and ${\displaystyle d_{H}(\mathbf {u^{2}G,c_{s}} )\leq t}$, which contradict with ${\displaystyle d_{H}(\mathbf {u^{1}G,u^{2}G} )\geq 2t+1}$.따라서 우리는 동일한 신드롬을 가진 둘 이상의 입력 쌍을 가질 수 없다.

Therefore, we can successfully compress the two dependent sources with constructed subcodes from an ${\displaystyle (n,k,2t+1)}$ binary linear code, with rate pair ${\displaystyle (R_{1},R_{2})}$ such that ${\displaystyle R_{1},R_{2}\g$$eq n-k,R_{1}+R_{2}\geq 2n-k}$, where ${\displaystyle R_{1}}$ and ${\displaystyle R_{2}}$ are integers, and ${\displaystyle k\leq n-\log(\sum _{i=0}^{t}{n \choose i})}$. Log indicates Log₂.

슬레피안-울프 부호화 예

이전의 비대칭 DSC 대 대칭 DSC 파트에서와 동일한 예를 들어, 이 파트는 비대칭 케이스와 대칭 케이스를 포함한 코스메트 코드와 신드롬을 포함한 해당 DSC 체계를 제시한다.슬레피안-DSC 설계용 늑대는 앞부분에서 볼 수 있다.

비대칭 케이스

$R{\displaystyle {}_{}}$ ${\displaystyle X_{}}$= ${\displaystyle 3}$ ${\displaystyle R_{X}=3}$ 및$$ $R{\displaystyle {}_{}}$ ${\displaystyle Y_{}}$= 7 ${\displaystyle R_{{}$인 경우$Y}=7$ $소스{\displaystyle }$ Y ${\displaystyle Y}$에서 입력 $변수{\displaystyle \mathbf{}}$ y ${\$의 길이는 7비트이므로$$ 다른 비트와 독립적으로 7비트로 무손실 전송될 수 있다.$수신기$에 이미 $y{\displaystyle \mathbf{}}$ ${\\${$x}$$$및$$ $y{\displaystyle \mathbf{}}$ ${\$$}이($가) $있기{\displaystyle \mathbf{}}$ 때문에 소스 $X{\displaystyle }$ ${\displaystyle X}$에서 $입력{\displaystyle \mathbf{}}$ x$${\$displaysty$ $\mathbf${$x$$}$에 대해 해밍 거리가 최대 하나라는$$ 사실을 기반으로 한다$.$$aystyle \mathbf {x} }$ are those with at most 1 distance from ${\displaystyle \mathbf {y} }$. If we model the correlation between two sources as a virtual channel, which has input ${\displaystyle \mathbf {x} }$ and output ${\displaystyle \mathbf {y} }$, as long as we get ${\displaystyle \mathbf {y} }$, all w$e{\displaystyle \mathbf{}}$ 성공적으로 "수정" $x{\displaystyle \mathbf{}}$ ${\$을(를) "수정 비트"로$$, x ${\$ $\$$mathbf {x}$과(와) $y{\displaystyle \mathbf{}}$ ${\$ \$mathbf$ {$y}$ 사이의 차이를 채널 오류로 간주한다$$.우리는 또한 코세츠 파티션의 문제를 모델링할 수 있다.즉, 입력 $X{\displaystyle }$ ${\displaystyle X}$의 공간을 여러$$ 코세트로 분할할 수 있는 채널 코드를 찾고자 하는데, 각 코세트는 이와 관련된 고유한 증후군을 가지고 있다.지정된 코셋과 $y{\displaystyle \mathbf{}}$ ${\$$}$을(를) 사용하는 경우, 두 소스 간의 상관관계가 주어진 입력일 $수{\displaystyle \mathbf{}}$ 있는 x$$ ${\$만 있다$.$

In this example, we can use the ${\displaystyle (7,4,3)}$ binary Hamming Code ${\displaystyle \mathbf {C} }$, with parity check matrix ${\displaystyle \mathbf {H} }$. For an input ${\displaystyle \mathbf {x} }$ from source ${\displaystyle X}$, only the syndrome given by ${$$\displaystyle \mathbf {s} =\mathbf {H} \mathbf {x}}$이(가) 전송되는데$$, 이는 3비트다.With received ${\displaystyle \mathbf {y} }$ and ${\displaystyle \mathbf {s} }$, suppose there are two inputs ${\displaystyle \mathbf {x_{1}} }$ and ${\displaystyle \mathbf {x_{2}} }$ with same syndrome ${\displaystyle \mathbf {s} }$. That means ${\dis$$playstyle \mathbf {H} \mathbf {x_{1}} =\mathbf {H} \mathbf {x_{2}} }$, which is ${\displaystyle \mathbf {H} (\mathbf {x_{1}} -\mathbf {x_{2}} )=0}$. Since the minimum Hamming weight of ${\displaystyle (7,4,3)}$ Hamming Code is 3, ${\displaystyle$$d_{H}(\mathbf {x_{1}} ,\mathbf {x_{2}} )\geq 3}$. Therefore, the input ${\displaystyle \mathbf {x} }$ can be recovered since ${\displaystyle d_{H}(\mathbf {x} ,\mathbf {y} )\leq 1}$.

마찬가지로 R ${\displaystyle X_{}}$= ${\displaystyle 7}$ ${\displaystyle R_{X}=7$ $R{\displaystyle {}_{}}$ ${\displaystyle Y_{}}$= ${\displaystyle 3}$ ${\displaystyle R_{{}}$을 사용한 비트 분포도$Y}=3}$은(는) $X{\displaystyle }$ ${\displaystyle X}$과($)$ Y {\$displaystyle Y}$의 역할을 반대로 하여 얻을 수 있다$$$.$

대칭 케이스

대칭의 경우, 우리가 원하는 것은 두 소스에 대해 동일한 비트 전송률이다: 각각 5비트씩 인코더와 조인트 디코더를 가지고 있다.우리는 비대칭 케이스에 사용했던 것처럼 여전히 이 시스템에 선형 코드를 사용한다.기본적인 생각은 비슷하지만, 이 경우에는 양쪽 소스에 대해 코제트 파티션을 해야 하는 반면, 수신된 신드롬 쌍(하나의 코제트에 대응)의 경우, 두 소스의 상관관계를 고려할 때 하나의 입력 변수 쌍만 가능하다.

선형 코드 ${\displaystyle {C\mathbf{}}_{}}$ 1 ${\$및$$ C ${\displaystyle {2\mathbf{}}_{}}$ ${\$}} $}$ 쌍과$$ 대칭 코딩을 달성할 수 있는 선형 코드 기반의 인코더-decoder 쌍이 있다고 가정합시다.The encoder output is given by: ${\displaystyle \mathbf {s_{1}} =\mathbf {H_{1}} \mathbf {x} }$ and ${\displaystyle \mathbf {s_{2}} =\mathbf {H_{2}} \mathbf {y} }$. If there exists two pair of valid inputs ${\displaystyle \mathbf {x_{1}} ,\mathbf {y_{1}} }$and ${\displaystyle \mathbf {x_{2}} ,\mathbf {y_{2}} }$ generating the same syndromes, i.e. ${\displaystyle \mathbf {H_{1}} \mathbf {x_{1}} =\mathbf {H_{1}} \mathbf {x_{2}} }$ and ${\displaystyle \mathbf {H_{1}} \mathbf {y_{1}$$}} =\mathbf {H_{1} \mathbf {y_{2$}} $\}\}\},$ 다음(${\displaystyle )}$을 얻을 수 있다$({\displaystyle w()}$는 해밍 중량을 나타낸다).

${\displaystyle {\mathbf{y}}_{}}$ ${\displaystyle {1\mathbf{}}_{}}$= ${\displaystyle x{\mathbf{}}_{}}$ ${\displaystyle {1\mathbf{}}_{}}$+ e ${\displaystyle {1\mathbf{}}_{}}$ ${\$} $=\mathbf {x_{1$} $+\mathbf {e_{1$ $여기$서 w${\displaystyle (}$ e${\displaystyle {}_{}{1\mathbf{}}_{}}$ )${\displaystyle 1}$ ${\displaystyle w(\mathbf {e_}})\leq 1}$

${\displaystyle {\mathbf{y}}_{}}$ ${\displaystyle {2\mathbf{}}_{}}$= ${\displaystyle x{\mathbf{}}_{}}$ ${\displaystyle {2\mathbf{}}_{}}$+ e ${\displaystyle {2\mathbf{}}_{}}$ ${\$}} $=\mathbf {x_{2$}} $+\mathbf {e_{2$ 여기서 $w{\displaystyle {}_{}}$ ${\displaystyle e{\mathbf{}}_{}}$ 2) ${\displaystyle {1\mathbf{}}_{}}$ ${\displaystyle w(\mathbf {e_{2}})\leq 1}$

따라서: ${\displaystyle {x\mathbf{}}_{}}$ 1${\displaystyle {}_{}}$+ ${\displaystyle x{\mathbf{}}_{}}$ ${\displaystyle {2\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle C{\mathbf{}}_{}}$ ${\displaystyle {1\mathbf{}}_{}}$ ${\$}}$\in \mathbf {C_{1}}}}$

${\displaystyle \mathbf {y_{1} +\mathbf {x_{1}:{1} +\mathbf {x_{2}} +\mathbf {e_}}} \in \mathbf {C_{2}}: }}}$

where ${\displaystyle \mathbf {e_{3}} =\mathbf {e_{2}} +\mathbf {e_{1}} }$ and ${\displaystyle w(\mathbf {e_{3}} )\leq 2}$. That means, as long as we have the minimum distance between the two codes larger than ${\displaystyle 3}$, we can achieve error-free decoding.

The two codes ${\displaystyle \mathbf {C_{1}} }$ and ${\displaystyle \mathbf {C_{2}} }$ can be constructed as subcodes of the ${\displaystyle (7,4,3)}$ Hamming code and thus has minimum distance of ${\displaystyle 3}$. Given the generator matrix ${\displaystyle \mathbf {G} }$ ofthe original Hamming code, the generator matrix ${\displaystyle \mathbf {G_{1}} }$ for ${\displaystyle \mathbf {C_{1}} }$ is constructed by taking any two rows from ${\displaystyle \mathbf {G} }$, and ${\displaystyle \mathbf {G_{2}} }$ is constructed by the remaining two rows of ${\$$displaystyle \mathbf$ {${\displaystyle \mathrm{G}}$$\}\}.$ 각 하위 코드에 해당하는(${\displaystyle 5}{\displaystyle \times }$ 7${\displaystyle }$) ${\displaystyle(5\times$ 7$)}$ 패리티 확인$$ 매트릭스를 제너레이터 매트릭스에 따라 생성하여 신드롬 비트를 생성하는 데 사용할 수 있다.

Wyner-Ziv 코딩 – 손실 분산 코딩

일반적으로 Wyner-Ziv 코딩 체계는 Slepian–에 정량제와 디 퀀타이저를 추가하여 얻는다.늑대 부호화 계획.따라서 Wyner-Ziv 코더 설계는 정량제와 해당 재구성 방법 설계에 초점을 맞출 수 있다.중첩 격자 정량기,^[21] trellis 코드 정량기^[22], Lloyd 정량화 방법 등 여러 정량화 설계가 제안되었다.^[23]

대규모 분산 정량화

불행히도 위의 접근방식은 분산 압축이 가장 유용한 시나리오인 대규모 센서 네트워크로 확장되지 않는다(설계 또는 운영상의 복잡성 요건에서).(일부 분산 코딩 방식과 함께) R비트에서 전송되는 N 선원이 있는 경우, 가능한 재구성의 $수$는 ${\displaystyle {\mathrm{2N}}^{}}$ R$[\$ 2$^{NR}})$로 확장된다$.$ N과 R의 중간 값(예: N=10, R = 2)의 경우에도 이전 설계 계획은 비현실적으로 된다.최근, 설계와 운영상의 복잡성을 디코더 성능에 대해 거래하는,^[24] 상관된 소스의 Fusion Coding에서 차용한 아이디어를 이용하는 접근법이 제안되었다.이것은 60개 선원에 이르는 네트워크 크기에 대한 분산 정량자 설계를 허용했고, 전통적인 접근법에 비해 상당한 이득을 얻었다.

중심 아이디어는 각 소스에 대해 수신된 비트(NR 비트, 위의 예에서)의 특정 서브셋을 유지하는 비트 서브셋 선택기의 존재다.$B{\displaystyle \mathcal{}}$ ${\$을(를) NR 비트의 모든 하위 집합의 집합으로$$ 설정하십시오.

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

그런 다음 비트 서브셋 선택기 매핑을 다음과 같이 정의한다.

${\displaystyle {\mathcal{S}:\{1,...,N\}\오른쪽 화살표 {\mathcal{B}}$

비트 서브셋 선택기를 선택할 때마다 선택한 비트 집합의 카디널리티에 지수적인 저장 요구사항(C)이 부과된다는 점에 유의하십시오.

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

이를 통해 디코더 저장장치의 제약조건을 고려할 때 왜곡을 최소화하는 비트를 현명하게 선택할 수 있다.허용 가능한 하위 집합 집합에 대한 추가 제한이 여전히 필요하다.효과적인 비용 함수를 최소화해야 하는 것은 왜곡과 디코더 스토리지의 가중치 합이다.

$J=D+\lambda C}$

시스템 설계는 인코더, 디코더 및 비트 서브셋 셀렉터를 정합화까지 반복적으로 최적화하는 방식으로 수행된다.

비대칭 DSC

이 구간은 비어 있다.추가하면 도움이 된다.(2010년 6월)

세 개 이상의 소스에 대한 비대칭 DSC

신드롬 접근법은 여전히 세 가지 이상의 출처에 사용될 수 있다.Consider ${\displaystyle a}$ binary sources of length-${\displaystyle n}$ ${\displaystyle \mathbf {x} _{1},\mathbf {x} _{2},\cdots ,\mathbf {x} _{a}\in \{0,1\}^{n}}$. Let ${\displaystyle \mathbf {H} _{1},\mathbf {H} _{2},\cdots$$,\mathbf {H} _{s}}$ be the corresponding coding matrices of sizes ${\displaystyle m_{1}\times n,m_{2}\times n,\cdots ,m_{a}\times n}$. Then the input binary sources are compressed into ${\di$$splaystyle \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}}$ of total ${\displaystyle m=m_{1}+m_{2}+\cdots m_{a}}$ bits.분명히 두 개의 소스 튜플이 같은 증후군을 공유하면 동시에 회복될 수 없다.즉, 모든 출처 튜플이 서로 다른 신드롬을 가지고 있다면, 무손실로 회복할 수 있다.

일반적인 이론적 결과는 존재하지 않는 것 같다.그러나, 제한된 종류의 소위 해밍 선원에 대해서는, 다른 선원과 다른 선원과 모든 선원이 동일한 것은 아니지만, 적어도 하나의 비트 위치에서만 존재하는 것으로 보여지고, 경우에 따라 실질적인 손실 없는 DSC가 존재한다.소스가 세 개 이상인 경우, 해밍 소스의 소스 튜플 수는 ${\displaystyle {2n}^{}n}$+${\displaystyle 1}$ ) ${\displaystyle$ 2$^{n}(an+1$) 입니다$.$따라서 ${\displaystyle {2m}^{}}$≥ ${\displaystyle {2n}^{}}$ ${\displaystyle {}^{}\mathrm{n}}$+ 1$){\displaystyle 2^{m}\geq 2^{n$}{n$}(an+1)}$의 패킹 바운드가 충족되어야 하는 것은$$ 명백하다.포장 바운드가 평등에 만족할 때, 우리는 그러한 코드를 완벽하다고 부를 수 있다(오류 수정에서 완벽한 코드와 유사함).^[25]

동등하게 묶인 패킹을 만족시키기 위한$$ $가장{\displaystyle }$ 간단한 a${\displaystyle ,}$ n${\displaystyle ,}$ ${\displaystyle m}$ ${\displaystyle a,n,m}$의 $집합$은 a${\displaystyle }$= ${\displaystyle 3,n}$ ${\displaystyle =}$ ${\displaystyle 5,m}$= ${\displaystyle 9}$[\$displaystyle a=3,n=5,m=9$}이다$.$ 그러나 그러한 신드롬 코드는 존재하지 않는 것으로 밝혀졌다.^[26]소스가 세 개 이상인 가장 단순한(완벽한) 신드롬 코드는 $n{\displaystyle }$= ${\displaystyle 21}$ ${\displaystyle n=21},$ $m$ = ${\displaystyle 27}$ ${\displaystyle m=27}$을(를) 가지고 있다$.$

${\displaystyle {\mathbf{Q}}_1=(\begin{array}{c}100000100001110110000\\ 010000110000100000111\\ 001000011000011101011\\ 000100001100010011110\\ 000010000110101101111\end{array}}$${\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\end{pmatrix}},}$ ${\displaystyle {\mathbf{Q}}_2=(\begin{array}{c}000101101111010001111\\ 100010110111101111000\\ 010001111\end{array}}$${\displaystyle \mathbf {Q} _{2}={\begin{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}},}$ ${\displaystyle {\mathbf{Q}}_3}$${\displaystyle {}_{}=(\begin{array}{c}100101001110100111111\\ 110010000111001111111\\ 011001100011111101110\\ 101100110001001111001\\ 010110111000100110100\\ 001\end{array}}$${\displaystyle \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}]}$, and ${\displaystyle \mathbf {G}$$={\begin{pmatrix}\mathbf {G} _{1}\\\mathbf {G} _{2}\\\mathbf {G} _{3}\end{pmatrix}}}$ such that ${\displaystyle \mathbf {G} _{1},\mathbf {G} _{2},\mathbf {G} _{3}}$ are any partition of ${\displaystyle \mathbf {G} }$.

${\displaystyle \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}}}}}$은(는) 해밍 소스(즉, 1비트 이하의 소스는 모두 다른 신드롬을 가질 수 있다$$.^[25]For example, for the symmetric case, a possible set of coding matrices are ${\displaystyle {\mathbf{H}}_1=(\begin{array}{c}000000000000000000100\\ 000000000000000000010\\ 000000000000000000001\\ 100000100001110110\end{array}}$${\displaystyle \begin{array}{c}000\\ 010000110000100000111\\ 001000011000011101011\\ 000100001100010011110\\ 000010000110101101111\\ 000001000011001001101\end{array}),}$${\displaystyle \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}},}$ ${\displaystyle {\mathbf{H}}_2=(\begin{array}{c}000000000000000\end{array}}$${\displaystyle \begin{array}{c}100000\\ 000000000000000010000\\ 000000000000000001000\\ 000101101111010001111\\ 100010110111101111000\\ 010001111011100000101\end{array}}$${\displaystyle \mathbf {H} _{2}={\begin{pmatrix}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\;0\;0\;0\\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}},}$ ${\displaystyle {\mathbf{H}}_3=(\begin{array}{c}000000000000100000000\\ 000000000000010000000\\ 0000000000000010000\end{array}}$${\displaystyle \begin{array}{c}00\\ 100101001110100111111\\ 110010000111001111111\\ 011001100011111101110\\ 101100110001001111001\\ 010110111000100110100\\ 0010\end{array}}$${\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}}.$$}$

참고 항목

• 선형코드
• 디코딩 증후군
• 저밀도 패리티 검사 코드
• 터보 코드

참조