无速率码(入门七)OSD解码算法详解(Ordered Statistics Decoder)

这篇具有很好参考价值的文章主要介绍了无速率码(入门七)OSD解码算法详解(Ordered Statistics Decoder)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. OSD解码器归类

  Ordered Statistics Decoder(OSD)作为一种次优的 ML 译码的方法(次优指误块率比ML译码算法高,见图一,可操作性强、性能逼近 ML 译码并且在较低信噪比下可以通过增加译码阶数不断地提高性能,缺点在于低信噪比下的OSD 译码计算复杂度 O ( K l ) O\left(K^{l}\right) O(Kl)会随阶数 l l l呈指数增长[2]。

osd算法,算法,算法,概率论
图一:线性分组码在ML算法和OSD算法下的译码性能对比

  针对无速率码时,迭代译码更适用于长码,在短码下译码性能不佳,ML译码更适合短码[2,3]。

2. 1995原始OSD译码流程 [ 1 , 2 ] ^{[1,2]} [1,2]

  统计学中的order statistics 是针对很多样本中的某一个特定随机变量来说的。比如从一个服从指数分布的总体中取一个样本集,其中包含 n n n个互相独立的随机变量,这个样本中的每一个随机变量还是服从指数分布。顺序统计量是指限定第 i i i个顺序统计量(order statistic)为该样本集合中第i小的元素,此时该随机变量的分布会因为 i i i的变化被扭曲而偏离原来的分布。但当n比较大时,同时取多个样本集,每个样本集中的 i i i阶统计量之间的差异都不会太大。
  对于一个码长序列,比特可靠性的排列可以近似为可靠性平均值的排列,OSD算法利用这一特性,改进了硬判决中的估计码字的生成过程。

2.1 基于可靠性的硬判决

  符号定义:

  • 等效生成矩阵 G \boldsymbol{G} G.
  • 接受到的符号序列 r = [ r 1 , r 2 , … , r N r ] \boldsymbol{r}=\left[r_{1}, r_{2}, \ldots, r_{N_{r}}\right] r=[r1,r2,,rNr].
  • 接受符号经过两次调序后得到 r ~ \tilde{\boldsymbol{r}} r~ r ~ \tilde{\boldsymbol{r}} r~再进行硬判决过程 y ~ i = { 0 , r ~ i > 0 1 , r ~ i ≤ 0 \tilde{y}_{i}=\left\{\begin{array}{l} 0, \tilde{r}_{i}>0 \\ 1, \tilde{r}_{i} \leq 0 \end{array}\right. y~i={0,r~i>01,r~i0,得到的序列为 y ~ = [ y 1 , y 2 , … , y N r ] \tilde{\boldsymbol{y}}=\left[y_{1}, y_{2}, \ldots, y_{N_{r}}\right] y~=[y1,y2,,yNr]
  • 硬判决的置信度即符号值的绝对值 α i = ∣ r i ∣ \alpha_{i}=|r_{i}| αi=ri(仅限于BPSK调制)  硬判决思想:利用排序后 α ~ \tilde{\boldsymbol{\alpha}} α~的前K位只包含少量错误信息位,在发送码字和接受码字之间最小化可能出错的bit数量。

Step1:在解码前先完成接受符号可靠性的降序排列 α ′ = Π 1 ( α ) \boldsymbol{\alpha}^{\prime}=\Pi_{1}(\boldsymbol{\alpha}) α=Π1(α),其中 Π 1 \Pi_{1} Π1表示顺序置换操作。在通过符号的可靠性得到置换操作后,进行 G ′ = Π 1 ( G ) \boldsymbol{G}^{\prime}=\Pi_{1}(\boldsymbol{G}) G=Π1(G) r ′ = Π 1 ( r ) \boldsymbol{r}^{\prime}=\Pi_{1}(\boldsymbol{r}) r=Π1(r)

PS1:step1中没有考虑 α i = α j \alpha_{i}=\alpha_{j} αi=αj的情况,因为 r \boldsymbol{r} r是调制符号 x \boldsymbol{x} x+ n \boldsymbol{n} n,对于信道随机变量 n \boldsymbol{n} n来说,出现相同数值的概率几乎为0.
PS2:针对该排序,可用归并排序或者快速排序算法(二分法排序),算法复杂度为 O ( N r log ⁡ N r ) \mathcal{O}\left(N_{r} \log N_{r}\right) O(NrlogNr)

Step2:将 G ′ \boldsymbol{G}^{\prime} G转化为系统矩阵 G ~ \boldsymbol{\widetilde{G}} G ,记录列置换顺序 Π 2 \Pi_{2} Π2。同样 r ~ = Π 2 ( r ′ ) , α ~ = Π 2 ( α ′ ) \tilde{\boldsymbol{r}}=\Pi_{2}\left(\boldsymbol{r}^{\prime}\right), \tilde{\boldsymbol{\alpha}}=\Pi_{2}\left(\boldsymbol{\alpha}^{\prime}\right) r~=Π2(r),α~=Π2(α)

PS1:这里可分为两步,第一步是列操作进行前K列的独立处理,即从第二列开始判断是否和前面的列线性无关,如果无关则保留,如果有关则从K+1列判断是否线性无关,如果无关则置换到当前对应列,否则继续寻找K+2列。第二步是行变换得到系统矩阵。该过程复杂度为 O ( N r ∗ m i n { K 2 , ( N r − K ) 2 } ) \mathcal{O}\left(N_r*min\{ K^2,(N_r-K)^{2}\}\right) O(Nrmin{K2,(NrK)2}) 如果 K > N r − K ,就通过 H 矩阵去求系统矩阵,反之通过 G 矩阵去求系统矩阵 如果K>N_r-K,就通过H矩阵去求系统矩阵,反之通过G矩阵去求系统矩阵 如果KNrK,就通过H矩阵去求系统矩阵,反之通过G矩阵去求系统矩阵
PS2:如果码率低于1/2,则为代码生成器矩阵,如果码率高于1/2,则为奇偶校验矩阵。

step3:硬判决先得到可靠序列 y ~ 1 : K = [ y 1 , y 2 , … , y K ] \tilde{\boldsymbol{y}}_{1:K}=\left[y_{1}, y_{2}, \ldots,y_{K}\right] y~1:K=[y1,y2,yK],然后利用 y ~ = y ~ 1 : K G ~ \tilde{\boldsymbol{y}}=\tilde{\boldsymbol{y}}_{1:K}\boldsymbol{\widetilde{G}} y~=y~1:KG 得到全部估计码字 c ~ o p t = y ~ \tilde{\boldsymbol{c}}_{\mathrm{opt}}=\tilde{\boldsymbol{y}} c~opt=y~

step4:最终估计码字为 c ^ = Π 1 − 1 ( Π 2 − 1 ( c ~ o p t ) ) \hat{\boldsymbol{c}}=\Pi_{1}^{-1}\left(\Pi_{2}^{-1}\left(\tilde{\boldsymbol{c}}_{\mathrm{opt}}\right)\right) c^=Π11(Π21(c~opt))

2.2 软判决的OSD译码

  原始OSD算法改进了硬判决方式,引入了再处理过程。所以step1、2、4不变,对step3进行更改。

osd算法,算法,算法,概率论
图二:OSD算法流程图

  ML软判决译码算法的思想:排序后 α ~ \tilde{\boldsymbol{\alpha}} α~的前K位只包含少量错误信息位,遍历 2 K 2^K 2K个可能的错误图样到硬判决值 y ~ 1 : K \tilde{\boldsymbol{y}}_{1:K} y~1:K上,然后生成 2 K 2^K 2K个估计码字,同两次置换后的接受序列 r ~ \tilde{\boldsymbol{r}} r~置信度差异最小的估计码字就是需要输出的估计码字。本质是在发送码字与估计接受码字之间最小化平方欧氏距离。

osd算法,算法,算法,概率论
图三:长度为K的测试错误图样的可能取值,Weight取值3中介绍

  OSD降低计算复杂度的思想:对于硬判决码字的前K个bit,其单个错误概率是随着位置索引值降低而降低的;对于考虑多bit连续错误的情况,组合的位数越多出错的概率越低——测试错误图样是存在优先级别的。所以减少不必要测试错误图样的生成,就能降低ML译码算法的复杂度——通过阶数限制多位bit错误的TEP的生成。

2.2.1 再处理过程

  • 再处理对象:硬判决得到的完整序列 y ~ = [ y 1 , … , y K , y K + 1 , … , y N ] \tilde{\boldsymbol{y}}=\left[y_{1}, \ldots,y_{K},y_{K+1}, \ldots,y_{N}\right] y~=[y1,,yK,yK+1,,yN]
  • 再处理过程参数: l , 1 ≤ l ≤ K l,1\leq l \leq K l,1lK表示阶数

再处理过程:

对于 l , 1 ≤ i ≤ l l,1\leq i \leq l l,1il:
  第i阶段的再处理过程 改变硬判决可靠序列 y ~ 1 : K = [ y 1 , y 2 , … , y K ] \tilde{\boldsymbol{y}}_{1:K}=\left[y_{1}, y_{2}, \ldots,y_{K}\right] y~1:K=[y1,y2,yK]中的 i i i个bit,然后重构对应的接受码字,并将其通过对应的调制方式调制,然后将该结果同排序后的接受码字 r ~ \tilde{\boldsymbol{r}} r~计算其在向量空间中的欧式距离。并记录欧式距离最小的码字作为估计码字 c ~ o p t \tilde{\boldsymbol{c}}_{\mathrm{opt}} c~opt
所以在每个阶段需要遍历 ( K i ) \left(\begin{array}{c}K \\ i\end{array}\right) (Ki)个可能TEP,整个流程需要遍历 ∑ i = 0 l ( K i ) \sum_{i=0}^{l}\left(\begin{array}{c}K \\ i\end{array}\right) i=0l(Ki)个TEP。

显然如果 l = K l=K l=K就是最大似然译码的思路了。

  仿真表明:对于N小于等于64的高速短块码, l = 2 l=2 l=2即可实现接近ML最佳性能的解码。块长继续增大时,至少需要 l = 3 l=3 l=3才能接近最佳性能。

2.2.2 停止准则(由于传统OSD算法中引入似然比定义可靠度改变了停止准则,该停止准则可跳过)

思想:在第i阶段,最后i个位置的可靠度之和大于某一迭代更新的可靠性阈值可视为解码成功。表征即使最后i个翻转了(图论中的图引入了对应的节点,与现存节点构成边相连),其边权重加上去也不会使得平方欧式距离增大。
  对于 l l l-OSD过程,如果存在 i < l i<l i<l,有 − ∑ j = 0 i δ K − j ( y ~ ) ≥ R a v a i l a b l e ( i + 1 ) -\sum_{j=0}^{i} \delta_{K-j}(\tilde{\boldsymbol{y}}) \geq R_{\mathrm{available}}(i+1) j=0iδKj(y~)Ravailable(i+1)成立,那么该阶段可以停止再处理过程,并在记录位置修改 y ~ \tilde{\boldsymbol{y}} y~,生成最大似然的解码结果。

定义(此处用不太上):

  • y ~ \tilde{\boldsymbol{y}} y~作为硬判决的结果,用上标 α \alpha α表示改变了其中 i i i个bit的位置索引, y ~ α \tilde{\boldsymbol{y}}^{\alpha} y~α即重构后的估计码字。重构码字调制后位 x ~ α = ( α 1 , α 2 , . . . , α N ) \tilde{\boldsymbol{x}}^{\alpha}=(\alpha_1,\alpha_2,...,\alpha_N) x~α=(α1,α2,...,αN)
  • 欧式距离的平方 E = d 2 ( x ~ α , r ~ ) E=d^2(\tilde{\boldsymbol{x}}^{\alpha},\tilde{\boldsymbol{r}}) E=d2(x~α,r~)
  • δ i ( y ~ α ) = δ i ( x ~ α ) = 1 / 4 ( ( y i − α i ) 2 − ( y i + α i ) 2 ) = − ∣ y i ∣ \delta_{i}\left(\tilde{\boldsymbol{y}}^{\boldsymbol{\alpha}}\right)=\delta_{i}\left(\tilde{\boldsymbol{x}}^{\boldsymbol{\alpha}}\right)=1 / 4\left(\left(y_{i}-\alpha_{i}\right)^{2}-\left(y_{i}+\alpha_{i}\right)^{2}\right)=- |y_{i}| δi(y~α)=δi(x~α)=1/4((yiαi)2(yi+αi)2)=yi
  • 可用资源 R available  ( i ) = min ⁡ { R i ( x ‾ S ) − E ( x ‾ S , x ‾ C ) , R i ( x ‾ C ) } R_{\text {available }}(i)=\min \left\{R_{i}\left(\overline{\boldsymbol{x}}_{\boldsymbol{S}}\right)-E\left(\overline{\boldsymbol{x}}_{\boldsymbol{S}}, \overline{\boldsymbol{x}}_{\boldsymbol{C}}\right), R_{i}\left(\overline{\boldsymbol{x}}_{\boldsymbol{C}}\right)\right\} Ravailable (i)=min{Ri(xS)E(xS,xC),Ri(xC)}。(用图论定义的阈值)其中 R i ( x ‾ α ) = ∑ δ j ( x ‾ α ) ∈ D + ( x ‾ α ) δ j ( x ‾ α ) + ∑ δ j ( x ‾ α ) ∈ D R − ( x ‾ α ) δ j ( x ‾ α ) R_{i}\left(\overline{\boldsymbol{x}}^{\boldsymbol{\alpha}}\right)=\sum_{\delta_{j}\left(\overline{\boldsymbol{x}}^{\boldsymbol{\alpha}}\right) \in D^{+}\left(\overline{\boldsymbol{x}}^{\boldsymbol{\alpha}}\right)} \delta_{j}\left(\overline{\boldsymbol{x}}^{\boldsymbol{\alpha}}\right)+\sum_{\delta_{j}\left(\overline{\boldsymbol{x}}^{\boldsymbol{\alpha}}\right) \in D_{R}^{-}\left(\overline{\boldsymbol{x}}^{\boldsymbol{\alpha}}\right)} \delta_{j}\left(\overline{\boldsymbol{x}}^{\boldsymbol{\alpha}}\right) Ri(xα)=δj(xα)D+(xα)δj(xα)+δj(xα)DR(xα)δj(xα) E ( x ‾ α , x ‾ β ) = 1 / 4 ( d 2 ( x ‾ α , z ‾ ) − d 2 ( x ‾ β , z ‾ ) ) E\left(\overline{\boldsymbol{x}}^{\boldsymbol{\alpha}}, \overline{\boldsymbol{x}}^{\boldsymbol{\beta}}\right)=1 / 4\left(d^{2}\left(\overline{\boldsymbol{x}}^{\boldsymbol{\alpha}}, \overline{\boldsymbol{z}}\right)-d^{2}\left(\overline{\boldsymbol{x}}^{\boldsymbol{\beta}}, \overline{\boldsymbol{z}}\right)\right) E(xα,xβ)=1/4(d2(xα,z)d2(xβ,z))

2.2.3 再处理算法复杂度

osd算法,算法,算法,概率论

3. 2007传统OSD算法 [ 4 ] ^{[4]} [4]

思路:由于OSD延身算法主要取决于可能的错误图样的排列和数量,[4]引入了迭代参考指标的重编码技术和自适应丢弃规则,前者简化了再处理中重编码过程,后者减少了平均重编码次数。[5]用TEP生成取代了OSD的结构化搜索,基于统计顺序特性引入了和信道SNR相关联的TEP的优先级权重,其思想是在两个不可靠的bit位进行再处理收益比在一个可靠的bit位进行再处理的收益更大。

2007传统OSD算法详解


原始OSD算法:

Step1:在解码前先完成接受符号可靠性的降序排列 α ′ = Π 1 ( α ) \boldsymbol{\alpha}^{\prime}=\Pi_{1}(\boldsymbol{\alpha}) α=Π1(α),其中 Π 1 \Pi_{1} Π1表示顺序置换操作。在通过符号的可靠性得到置换操作后,进行 G ′ = Π 1 ( G ) \boldsymbol{G}^{\prime}=\Pi_{1}(\boldsymbol{G}) G=Π1(G) r ′ = Π 1 ( r ) \boldsymbol{r}^{\prime}=\Pi_{1}(\boldsymbol{r}) r=Π1(r)

Step2:将 G ′ \boldsymbol{G}^{\prime} G转化为系统矩阵 G ~ \boldsymbol{\widetilde{G}} G ,记录列置换顺序 Π 2 \Pi_{2} Π2。同样 r ~ = Π 2 ( r ′ ) , α ~ = Π 2 ( α ′ ) \tilde{\boldsymbol{r}}=\Pi_{2}\left(\boldsymbol{r}^{\prime}\right), \tilde{\boldsymbol{\alpha}}=\Pi_{2}\left(\boldsymbol{\alpha}^{\prime}\right) r~=Π2(r),α~=Π2(α)

step3:硬判决先得到可靠序列 y ~ 1 : K = [ y 1 , y 2 , … , y K ] \tilde{\boldsymbol{y}}_{1:K}=\left[y_{1}, y_{2}, \ldots,y_{K}\right] y~1:K=[y1,y2,yK],然后再处理过程(对于 l , 1 ≤ i ≤ l l,1\leq i \leq l l,1il):
  第i阶段的再处理过程 改变硬判决可靠序列 y ~ 1 : K = [ y 1 , y 2 , … , y K ] \tilde{\boldsymbol{y}}_{1:K}=\left[y_{1}, y_{2}, \ldots,y_{K}\right] y~1:K=[y1,y2,yK]中的 i i i个bit,然后重构对应的接受码字,并将其通过对应的调制方式调制,然后将该结果同排序后的接受码字 r ~ \tilde{\boldsymbol{r}} r~计算其在向量空间中的欧式距离。并记录欧式距离最小的码字作为估计码字 c ~ o p t \tilde{\boldsymbol{c}}_{\mathrm{opt}} c~opt。如果过程中第 i i i阶段符合停止条件,提前输出估计码字。

传统OSD算法在此基础上可靠性变化,再处理过程变化

step4:最终估计码字为 c ^ = Π 1 − 1 ( Π 2 − 1 ( c ~ o p t ) ) \hat{\boldsymbol{c}}=\Pi_{1}^{-1}\left(\Pi_{2}^{-1}\left(\tilde{\boldsymbol{c}}_{\mathrm{opt}}\right)\right) c^=Π11(Π21(c~opt))

论文顺序:原始OSD→【6】→传统OSD


定义: ( N , K ) 线性分组码 (N,K)线性分组码 (N,K)线性分组码

  • 二元码字 c = [ c 1 c 2 … c N ] \mathbf{c}=\left[\begin{array}{llll}c_{1} & c_{2} & \ldots & c_{N}\end{array}\right] c=[c1c2cN],假设每个码字出现的概率相等, Pr ⁡ ( c ) = 2 − K , c ∈ C \operatorname{Pr}(\mathbf{c})=2^{-K},\mathbf{c} \in \mathcal{C} Pr(c)=2K,cC
  • BPSK调制后的单位能量的双极性符号经过信道后接受为 r = [ r 1 r 2 … r N ] \mathbf{r}=\left[\begin{array}{llll}r_{1} & r_{2} & \ldots & r_{N}\end{array}\right] r=[r1r2rN],其中 r i = B P S K ( c i ) + n i r_i=BPSK(c_i)+n_i ri=BPSKci+ni
  • 定义第i个bit位的似然比 δ i ≜ ln ⁡ Pr ⁡ ( c i = 0 ∣ r i ) Pr ⁡ ( c i = 1 ∣ r i ) = 4 r i / N 0 \delta_{i} \triangleq \ln \frac{\operatorname{Pr}\left(c_{i}=0 \mid r_{i}\right)}{\operatorname{Pr}\left(c_{i}=1 \mid r_{i}\right)}=4 r_{i} / N_{0} δilnPr(ci=1ri)Pr(ci=0ri)=4ri/N0
  • 接受符号的硬判决用 y \mathbf{y} y表示

变化一:可靠性相较原始方案多了一个放缩: α i = δ i = ln ⁡ Pr ⁡ ( c i = 0 ∣ r i ) Pr ⁡ ( c i = 1 ∣ r i ) = 4 ∣ r i ∣ / N 0 \alpha_i=\delta_{i} = \ln \frac{\operatorname{Pr}\left(c_{i}=0 \mid r_{i}\right)}{\operatorname{Pr}\left(c_{i}=1 \mid r_{i}\right)}=4 |r_{i}| / N_{0} αi=δi=lnPr(ci=1ri)Pr(ci=0ri)=4∣ri∣/N0
  在原始OSD算法上采用bit似然值定义位可靠性,在计算可靠性后根据可靠性完成两次置换,使得 α ~ 1 ≥ α ~ 2 ≥ ⋯ ≥ α ~ K \tilde{\alpha}_{1} \geq \tilde{\alpha}_{2} \geq \cdots \geq \tilde{\alpha}_{K} α~1α~2α~K and α ~ K + 1 ≥ α ~ K + 2 ≥ ⋯ ≥ α ~ N \tilde{\alpha}_{K+1} \geq \tilde{\alpha}_{K+2} \geq \cdots \geq \tilde{\alpha}_{N} α~K+1α~K+2α~N

变化二:对于原始OSD中step2的实现用了贪婪算法(但看思路和原始OSD一模一样)

osd算法,算法,算法,概率论

变化三:定义TEP的加权汉明距离 D ( α ~ , e ) ≡ D ( e ) ≜ ∑ 1 ≤ i ≤ N , c e , i ≠ y i α ~ i \mathcal{D}(\tilde{\alpha}, \mathbf{e}) \equiv \mathcal{D}(\mathbf{e}) \triangleq \sum_{{\mathbf{1} \leq \mathbf{i} \leq \mathbf{N}, \mathbf{c}_{\mathbf{e}, \mathbf{i}} \neq \mathbf{y}_{\mathbf{i}}}} \tilde{\alpha}_{\mathbf{i}} D(α~,e)D(e)1iNce,i=yiα~i,且将其分解为TEP似然值和冗余WHD, L ( e ) ≜ ∑ 1 ≤ i ≤ K , e i = 1 α ~ i , D R ( e ) ≜ ∑ K + 1 ≤ i ≤ N , c ˉ e , i = 1 α ~ i \mathcal{L}(\mathbf{e}) \triangleq \sum_{{1 \leq i \leq K , e_{i}=1}} \tilde{\alpha}_{i}, \quad \mathcal{D}_{R}(\mathbf{e}) \triangleq \sum_{{K+1 \leq i \leq N , \bar{c}_{\mathbf{e}, i=1}}} \tilde{\alpha}_{i} L(e)1iKei=1α~i,DR(e)K+1iNcˉe,i=1α~i。定义TEP后将0阶硬判决过程表示为: c ~ 0 ≜ y ~ B G ~ = [ y ~ B y ~ B P ~ ] \tilde{\mathbf{c}}_{0} \triangleq \tilde{\mathbf{y}}_{B} \tilde{\mathbf{G}}=\left[\begin{array}{ll}\tilde{\mathbf{y}}_{B} & \tilde{\mathbf{y}}_{B} \tilde{\mathbf{P}}\end{array}\right] c~0y~BG~=[y~By~BP~],将再处理过程表示为 c ~ e ≜ ( y ~ B ⊕ e ) G ~ = [ y ~ B ⊕ e ( y ~ B ⊕ e ) P ~ ] \tilde{\mathbf{c}}_{\mathbf{e}} \triangleq\left(\tilde{\mathbf{y}}_{B} \oplus \mathbf{e}\right) \tilde{\mathbf{G}}=\left[\tilde{\mathbf{y}}_{B} \oplus \mathbf{e} \quad\left(\tilde{\mathbf{y}}_{B} \oplus \mathbf{e}\right) \tilde{\mathbf{P}}\right] c~e(y~Be)G~=[y~Be(y~Be)P~]

(原始OSD没有管TEP的WHD,而是在得到估计码字后计算平方欧式距离,用于衡量估计码字的准确度)

TEP的生成过程

变化四:TEP的生成,思想是将TEP按照似然值排序: L ( e ( 0 ) ) ≤ L ( e ( 1 ) ) ≤ L ( e ( 2 ) ) ≤ ⋯ ≤ L ( e ( 2 K − 1 ) ) \mathcal{L}\left(\mathbf{e}^{(0)}\right) \leq \mathcal{L}\left(\mathbf{e}^{(1)}\right) \leq \mathcal{L}\left(\mathbf{e}^{(2)}\right) \leq \cdots \leq \mathcal{L}\left(\mathbf{e}^{\left(2^{K}-1\right)}\right) L(e(0))L(e(1))L(e(2))L(e(2K1))(该排序通过 N ( e ) ≜ 2 K w ( e ) ∑ i = 1 K 2 − i e i \mathcal{N}(\mathbf{e}) \triangleq 2^{K w(\mathbf{e})} \sum_{i=1}^{K} 2^{-i} e_{i} N(e)2Kw(e)i=1K2iei实现)。论文针对上述排序方式设计了TEP的迭代生成方案。

  对于 L ( e ‾ ) ≥ L ∗ \mathcal{L}(\overline{\mathrm{e}}) \geq \mathcal{L}^{*} L(e)L,将该TEP e ‾ \overline{\mathrm{e}} e丢弃,利用非零位置索引 I ( e ) = [ I 1 , I 2 , ⋯ , I w ( e ) ] , I 1 > I 2 > ⋯ > I w ( e ) \mathcal{I}(\mathbf{e})=[\mathcal{I}_{1},\mathcal{I}_{2},\cdots,\mathcal{I}_{w(\mathbf{e})}],\mathcal{I}_{1}>\mathcal{I}_{2}>\cdots>\mathcal{I}_{w(\mathbf{e})} I(e)=[I1I2Iw(e)]I1>I2>>Iw(e)来定义新TEP的生成:

一般情况(一句话总结就是找关键位的索引值(依据关键位和生成公式得到的新的TEP一定是沿着TEP概率分布上升),TEP后置位可靠性比较低不叫关键位,即已经置1的不变(让它去修改MRB的对应位置),如第三个TEP的后两个1不变,对于非后置位的,找到连续的‘1’,最前面的一个1所在的位置就是关键位(如下面三个例子中画横线的1就是关键位置),然后根据下述索引计算式得到新的TEP中‘1’的位置索引。):
TEP生成公式:
I = [ K , K − 1 , … , K − κ + 2 , I ‾ κ − 1 , I ‾ κ + 1 , … , I ‾ w ( e ‾ ) ] \mathcal{I}=\left[K, K-1, \ldots, K-\kappa+2, \overline{\mathcal{I}}_{\kappa}-1, \overline{\mathcal{I}}_{\kappa+1}, \ldots, \overline{\mathcal{I}}_{w(\overline{\mathbf{e}})}\right] I=[K,K1,,Kκ+2,Iκ1,Iκ+1,,Iw(e)]
κ = min ⁡ { k : I ‾ k + 1 < I ‾ k − 1 } \kappa=\min \left\{k: \overline{\mathcal{I}}_{k+1}<\overline{\mathcal{I}}_{k}-1\right\} κ=min{k:Ik+1<Ik1}

  • 公式分析:
    -显然在一般情况下,有 1 ≤ κ ≤ w ( e ‾ ) 1 \leq \kappa \leq w(\overline e) 1κw(e)
    -由 I \mathcal{I} I得到当 κ = 1 \kappa=1 κ=1时, K − κ + 2 = K + 1 K-\kappa+2=K+1 Kκ+2=K+1,同时 κ = w ( e ‾ ) \kappa=w(\overline e) κ=w(e)时,出现了 I ‾ w ( e ‾ ) − 1 \overline{\mathcal{I}}_{w(\overline e)}-1 Iw(e)1 I ‾ w ( e ‾ ) \overline{\mathcal{I}}_{w(\overline e)} Iw(e)。文中没有说这两种情况怎么处理,但是根据算法中的case判断,前一种情况符合case1,就和下图的第二个例子一样,后一种情况仅保留 I ‾ w ( e ‾ ) − 1 \overline{\mathcal{I}}_{w(\overline e)}-1 Iw(e)1,否则增加会加一个权重

下述三个例子 κ 分别为 3 , 2 , 5 \kappa分别为3,2,5 κ分别为325注意下面的 κ \kappa κ是需要根据算法中的case1-4来判断是否还需要更新TEP然后继续迭代的,第一次得到的 κ \kappa κ不一定符合case判断,经过四次判断会不断更新TEP和 κ \kappa κ,下图只有TEP的最终生成结果
osd算法,算法,算法,概率论

针对第一个,可以套公式得到(这个例子里面后置位两个0,没有1,然后前置位连着三个1,然后一个0,又一个1,公式就是将前置位最前面的那个1置0,然后将前一位的0置1osd算法,算法,算法,概率论

特殊情况(特殊在关键位置会导致按照公式生成的TEP权重变大,即进入了TEP的下一阶的处理过程):
I = [ K , K − 1 , … , K − κ + 2 , I ‾ κ − 1 , I ‾ κ + 1 , … , I ‾ w ( e ‾ ) ] \mathcal{I}=\left[K, K-1, \ldots, K-\kappa+2, \overline{\mathcal{I}}_{\kappa}-1, \overline{\mathcal{I}}_{\kappa+1}, \ldots, \overline{\mathcal{I}}_{w(\overline{\mathbf{e}})}\right] I=[K,K1,,Kκ+2,Iκ1,Iκ+1,,Iw(e)]
κ = min ⁡ { k : I ‾ k + 1 < I ‾ k − 1 , I ‾ k − 1 < K − k + 2 } \kappa=\min \left\{k: \overline{\mathcal{I}}_{k+1}<\overline{\mathcal{I}}_{k}-1, \overline{\mathcal{I}}_{k-1}<K-k+2\right\} κ=min{k:Ik+1<Ik1,Ik1<Kk+2}

举个例子 κ 分别为 3 \kappa分别为3 κ分别为3
osd算法,算法,算法,概率论

针对找不到关键位置的情况,即直接从 l l l=3到 l l l=4的,按照初始化的最后几位进行生成。

变化五:在此基础上使用1)自适应跳过规则消除不必要的TEP(同S-OSD),2)引入迭代参考指标简化重新编码操作。

  1. 自适应TEP丢弃规则:对于TEP段 e h \boldsymbol{e}^{h} eh的估计下界来预估最可能的 e h ∗ \boldsymbol{e}^{h *} eh似然值 L ( e h ∗ ) \mathcal{L}\left(\boldsymbol{e}^{h *}\right) L(eh) e h ∗ \boldsymbol{e}^{h *} eh对应最小化WHD D ( ⋅ ) \mathcal{D}(\cdot) D())。丢弃规则中 L ( e h ) ≥ L ( e h ∗ ) \mathcal{L}\left(\boldsymbol{e }^{h}\right) \geq \mathcal{L}\left(\boldsymbol{e}^{h *}\right) L(eh)L(eh) L ( e h ∗ ) \mathcal{L}\left(\boldsymbol{e}^{h *}\right) L(eh):
    L ( e h ∗ ) = ∑ i = 1 K α ~ i ∑ i = 1 K α ~ i + λ ∑ i = K + 1 N α ~ i D ( e h ∗ ) \mathcal{L}\left(\boldsymbol{e}^{h *}\right)=\frac{\sum_{i=1}^{K} \tilde{\alpha}_{i}}{\sum_{i=1}^{K} \tilde{\alpha}_{i}+\lambda \sum_{i=K+1}^{N} \tilde{\alpha}_{i}} \mathcal{D}\left(\boldsymbol{e}^{h *}\right) L(eh)=i=1Kα~i+λi=K+1Nα~ii=1Kα~iD(eh)丢弃规则确定在每个段中实现丢弃的似然阈值,并且阈值可以随信道条件自适应地改变。抛弃没有处理必要的TEP,可以显著降低复杂度。

  2. 迭代过程:
    osd算法,算法,算法,概率论
    如下图中的经过case1-4处理后对应的TEP
    osd算法,算法,算法,概率论

另外一种TEP的生成思路:

[5] TEP生成算法思想:使用排列位的平均可靠性向量来生成最有可能的错误图样列表(在给定SNR下离线执行)

利用可靠性的CDF函数定义了平均可靠性,利用反转bit位的可靠性之和定义了一个错误图样的优先级。解码过程从根据可靠性的递增顺序排列接收位开始。对于每一个TEP计算其优先级,并将其放在列表中的适当位置,列表长度有限,如果生成的TEP超过列表长度,进行二分插入法,溢出低优先级的TEP。

[5] 中有一个TEP列表的排列操作用于生成TEP候选集,感觉思想和自适应阈值是一样的。但没像[4]一样指出阈值计算式,且操作的时间复杂度(会多引入二分插入排序)更高。

4. 参考文献:

[1] M. P. C. Fossorier and Shu Lin, “Soft-decision decoding of linear block codes based on ordered statistics,” in IEEE Transactions on Information Theory, vol. 41, no. 5, pp. 1379-1396, Sept. 1995, doi: 10.1109/18.412683.
[2] 李连琴.(2020).高可靠低时延喷泉码的分阶统计译码器研究(硕士学位论文,哈尔滨工业大学).https://kns.cnki.net/KCMS/detail/detail.aspx?dbname=CMFD202101&filename=1020399568.nh
[3] F. Lázaro, G. Liva, G. Bauch and E. Paolini, “Bounds on the Error Probability of Raptor Codes Under Maximum Likelihood Decoding,” in IEEE Transactions on Information Theory, vol. 67, no. 3, pp. 1537-1558, March 2021, doi: 10.1109/TIT.2020.3049061.
[4] Y. Wu and C. N. Hadjicostis, “Soft-Decision Decoding Using Ordered Recodings on the Most Reliable Basis,” in IEEE Transactions on Information Theory, vol. 53, no. 2, pp. 829-836, Feb. 2007, doi: 10.1109/TIT.2006.889699.
[5] A. Kabat, F. Guilloud and R. Pyndiah, “New Approach to Order Statistics Decoding of Long Linear Block Codes,” IEEE GLOBECOM 2007 - IEEE Global Telecommunications Conference, 2007, pp. 1467-1471, doi: 10.1109/GLOCOM.2007.282.
[6] D. Gazelle and J. Snyders, “Reliability-based code-search algorithms for maximum-likelihood decoding of block codes,” IEEE Trans. Inf. Theory, vol. 43, pp. 239–249, Jan. 1997.文章来源地址https://www.toymoban.com/news/detail-661407.html

到了这里,关于无速率码(入门七)OSD解码算法详解(Ordered Statistics Decoder)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Ceph入门到精通-更换osd、扩容osd

    1. 1 查看故障盘osd id 1.2 销毁osd 1.3 更换故障硬盘 1.4 查看新硬盘盘符 1.5 擦除新硬盘 1.6 预备替换原osd 1.7 查看osd fsid 1.8 激活osd 3.1 停止所有osd服务 3.2 销毁所有osd 3.3 擦除磁盘数据 3.4 清除crush数据 3.5 删除osd应用 4. 调整PG

    2024年02月19日
    浏览(40)
  • Ceph入门到精通-OSD waring 设置建议

    以下检查表明 OSD 节点存在问题。 1 在 /var/lib/ceph/osd 中找到的多个ceph_fsid值。 这可能意味着您正在托管许多集群的 OSD 此节点或某些 OSD 配置错误以加入 您期望的集群。 2 设置可能会导致数据丢失,因为如果 未达到最小值,Ceph 将不会确认对客户端的写入。 osd pool default 

    2024年02月11日
    浏览(46)
  • Ceph入门到精通-使用 Ceph 编排器管理 OSD

    作为存储管理员,您可以使用 Ceph 编排器来管理红帽 Ceph 存储集群的 OSD。 当红帽 Ceph 存储集群启动并运行时,您可以在运行时将 OSD 添加到存储集群。 Ceph OSD 通常由一个存储驱动器的一个守护进程及其节点中的关联日志组成。如果节点有多个存储驱动器,则为每个驱动器映

    2024年02月05日
    浏览(52)
  • Ceph入门到精通-ceph故障处理 - osd down处理

    发现osd掉之后,我们首先要确认是哪个主机的哪块盘,来判断是这个盘坏了还是什么原因 来看一下是哪两块 登录对应机器确认下是哪块盘 2.我们发现盘还在,首先尝试能否重启ceph-osd服务 ,这里已经拉起来了 3.如果重启无望或者盘漂移,重新卸载安装 3.1 看看日志 是不是有

    2024年02月01日
    浏览(38)
  • 详解信道容量,信道速率,安全速率的区别

    目录 一. 信道容量与信道速率 二. 小结 三. 安全速率与物理层安全 3.1 香农物理层安全模型 3.2 安全信道速率 四. 补充安全中断概率(Secrecy Outage Probability, SOP) 五. 补充安全分集度(Secrecy Diversity Order, SDO) 六. 附信道安全传输经常会出现的缩略词 先看信道容量C的公式: 其中

    2024年02月03日
    浏览(33)
  • 深度学习体系结构——CNN, RNN, GAN, Transformers, Encoder-Decoder Architectures算法原理与应用

    卷积神经网络(CNN)是一种特别适用于处理具有网格结构的数据,如图像和视频的人工神经网络。可以将其视作一个由多层过滤器构成的系统,这些过滤器能够处理图像并从中提取出有助于进行预测的有意义特征。 设想你手头有一张手写数字的照片,你希望计算机能够识别出

    2024年04月28日
    浏览(50)
  • 【计算机网络】—— 详解码元,传输速率的计算|网络奇缘系列|计算机网络

    🌈个人主页:  Aileen_0v0 🔥系列专栏:  一见倾心,再见倾城  ---  计算机网络~ 💫个人格言: \\\"没有罗马,那就自己创造罗马~\\\" 目录 码元  速率和波特 思考1   思考2  思考3 带宽(Bandwidth)  📝总结 码元 是指用一个 固定时长的信号波形 _(数字脉冲),代表不同离散数值的基本波

    2024年02月04日
    浏览(56)
  • 二叉树入门算法题详解

    首先知道二叉树是什么: 代码随想录 (programmercarl.com) 了解后知道其实二叉树就是特殊的链表,只是每个根节点节点都与两个子节点相连而其实图也是特殊的链表,是很多节点互相连接;这样说只是便于理解和定义,严格来说他们都是不同的数据结构了,在使用中还是要牢记

    2024年02月22日
    浏览(36)
  • 【后端版】分布式医疗云平台【【统计模块】his-statistics 模块、【子父项目】statistics-api 、statistics-domain、statistics-mapper】(十五)

    目录 3.7.【统计模块】his-statistics 模块及子项目的创建和配置 3.7.1.【子父项目】his-statistics 模块的创建

    2024年02月11日
    浏览(41)
  • 【算法与数据结构】1 算法0基础入门,详解什么是算法?什么是线性查找法?

    欢迎来到爱书不爱输的程序猿的博客, 本博客致力于知识分享,与更多的人进行学习交流 本文收录于算法与数据结构体系专栏, 本专栏 是服务于0基础者,一起完成从0到1的跨越 就是 一系列 可以解决问题的 清晰的 可执行的 计算机指令 那么生活中有哪些算法? 问路 :坐公交车到

    2023年04月09日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包