低复杂度极性码混合OSD-SC解码算法

需积分: 9 154 浏览量更新于2024-08-12 收藏 373KB PDF 举报

"极性码的混合OSD-SC解码算法是一种用于极化码的低复杂度解码方法，旨在提升SC（逐位消除）解码算法的错误纠正性能。该算法通过用较小规模的OSD（有序统计解码）替换部分SC解码器，实现了性能与复杂度之间的平衡。OSD解码器的大小可调整，以控制所提算法的解码复杂度和错误纠正性能之间的权衡。此外，文中还提出了一种简化该算法的方法。仿真结果显示，对于码长N分别为1024、512、256，码率R为1/3的情况，与SC解码器相比，在目标误比特率(BER)10^-5时，该算法提供了约0.3dB的增益。同时，文章也模拟和分析了OSD大小对解码性能的影响。关键词包括：极化码、有序统计解码、逐位消除解码、低复杂度。" 极化码是由Erdal Arikan在2009年提出的，它是一种利用信道极化现象实现高效编码的理论。这种编码技术可以使得在二进制输入离散无记忆信道上，一部分信道容量几乎被完全用于传输信息，而其余部分则变得极差，从而实现接近香农限的编码效率。 SC解码是极化码最常用的解码策略，它按照码字的位序逐位进行解码，具有较低的计算复杂度，但其错误纠正性能相对于其他高级解码方法如迭代译码或OSD而言较弱。OSD解码则是一种基于统计的错误检测和校正方法，能够提供比SC更好的性能，但代价是更高的计算复杂度。混合OSD-SC算法则结合了这两种方法的优点。在解码过程中，不是所有的位都采用SC解码，而是选择部分位使用OSD解码，尤其是那些对解码性能影响较大的位。这样既能利用OSD的高性能，又能控制整体的解码复杂度。通过调整OSD解码器的大小，可以在性能和复杂度之间找到一个理想的平衡点。为了进一步降低算法复杂度，文中提出的方法可能涉及优化OSD解码步骤，比如减少重试次数或者采用更高效的统计计算方法。仿真结果验证了这一方法的有效性，尤其是在较长码长和特定码率下，与纯SC解码相比，混合OSD-SC算法在保持较低复杂度的同时，显著提高了误码率性能。极性码的混合OSD-SC解码算法是对传统SC解码的改进，它通过巧妙地融合OSD和SC的优势，为实际应用中的极化码解码提供了新的思路，特别是在需要兼顾性能和计算复杂度的场景下，这种算法具有很高的实用价值。

A Hybrid OSD-SC Decoding Algorithm for Polar

Codes

Yusheng Xing

∗

, Guofang Tu

∗

School of Electronic, Electrical and Communication Engineering,

University of Chinese Academy of Sciences, P.R.China

Email: yushengjsman@gmail.com

Abstract—In this paper, we propose a low complexity hybrid

ordered statistics decoding (OSD) successive cancellation (SC)

decoding algorithm for the polar codes. By replacing smaller

size SC decoder with OSD decoder, we can improve the error

correcting performance of the SC algorithm. The size of the

OSD decoder can be changed to control the trade-off between

the decoding complexity and the error correcting performance

of the proposed algorithm. We also provide a method to further

simplify the proposed algorithm. Simulation results show that

the proposed algorithm offers about 0.3 dB gain comparing to

the SC at target bit error rate (BER) 10

−5

with code length

N = 1024, 512, 256 and code rate R = 1/3. The impact of the

OSD size is also simulated and analyzed.

Keywords—polar codes, ordered statistics decoding, successive

cancellation, low complexity

I. INTRODUCTION

Polar codes were developed by Arikan in 2009 [1]. And they

are the ﬁrst channel coding class which provides the capacity-

achieving ability with deterministic construction method in

binary memoryless symmetric channels. Successive cancella-

tion (SC) algorithm is the ﬁrst decoding algorithm for polar

codes provided by Arikan [1] and is used by him to prove the

capacity-achieving ability of polar codes. The SC algorithm

has a complexity O(N log N) where N is the codeword

length. The SC algorithm is a sub-optimum decoding algo-

rithm since it discards the information provided by the frozen

bits with indices larger than the index of the current informa-

tion bit [2]. To improve the error correcting performance of

polar codes, various decoding algorithms have been proposed.

In [1], belief propagation (BP) algorithm is considered to

decoding polar codes. BP has a complexity O(I

max

N log N )

where I

max

is the max iteration number. BP is also a sub-

optimum algorithm which shows slight lower block error rate

(BLER) comparing to SC.In [3], The successive cancellation

list (SCL) decoding algorithm is proposed. The SC algorithm

can be viewed as the SCL algorithm with L = 1. The

SCL algorithm is similar to the SC with the difference that

the SCL with list size L keeps L paths with the largest

probability. This difference is the cause of error correcting

performance improvement. The successive cancellation stack

(SCS) algorithm proposed in [4] is similar to SCL. Both SCL

and SCS have complexity O(LN log N) where L is the list

size. In [5], the authors proposed to use cyclic redundancy

check (CRC) bits to aid the decoding which substantially

improves the performance of polar codes. In order to show

performance advantage, the SCL needs larger list size which

causes larger decoding complexity. So, to lower the BLER

while maintain low decoding complexity, we propose a hybrid

ordered statistics decoding (OSD)-SC decoding algorithm with

complexity O(LN) in this paper, where L is the size of the

OSD decoder. This paper is organized as follows. Section

II introduces some backgrounds of polar code construction

and OSD algorithm. In Section III, the proposed algorithm is

described and we analyse its complexity. we also propose a

simpliﬁcation of the proposed algorithm in this section. We

put the numerical results in Section IV. Section V concludes

the paper.

II. PRELIMINARY

In this section, we give some brief introduction of polar code

construction and the OSD decoding algorithm. Hereafter, y

denotes the received sequence {y

, y

, ..., y

}, G

denotes

the generator matrix of polar codes with codeword length

N, u

denotes the message vector {u

, u

, ..., u

} which

includes the frozen bits, x

denotes the codeword vector

, x

, ..., x

}. We will explain these symbols later.

A. Polar code construction and the SC decoding algorithm

The polar codes are linear block codes with codeword length

N = 2

. The main idea of polar codes is to construct N bit-

channels with different channel capacity from N identical uses

of the original channel. The construction of the polar codes is

to select the bit positions corresponding to the so-called bit-

channels with the highest capacity. We put information bits in

these positions and put known values (frozen bits, usually 0)

in the remaining positions to form a message vector . Arikan

used the Bhattacharyya parameter to evaluate the bit-channels

which is not computational efﬁcient for most channels. The

Gaussian approximation method proposed in [6] is efﬁcient

and practical for the evaluation purpose. Once the bit-channel

selection is done and the message vector u

is formed, we can

get the codeword vector x

using the recursive structure of

the polar codes with O(N log N ) complexity. The generator

matrix G can be obtained by choosing the corresponding rows

from the linear transformation matrix G

= B

(⊗n)

, where

is the bit-reversal matrix and F

(⊗n)

is the n-th Kronecker

power of F =



1 0

1 1



下载后可阅读完整内容，剩余4页未读，立即下载

weixin_38599412

粉丝: 6
资源: 930

低复杂度极性码混合OSD-SC解码算法

短极性码的低复杂度有序统计解码算法

极性反转的DC-DC转换电路

基于极性码的量化SC解码器

研究紫外线通信中极性码的最佳SCL解码算法

极性编码HARQ传输的SC-List解码分析与自适应设计

低复杂度极性码连续消除列表解码算法

基于混合多值离散粒子群优化的混合极性Reed-Muller最小化算法

基于随机计算的极性码高通量连续抵消解码器

基于最佳路径量度的极性码的低复杂度球形解码

改进的度量排序，用于极性码的连续取消列表解码

最新资源