Punctured Binary Simplex Codes as LDPC codes Massimo Battaglioni Dept. of Information Engineering

2025-05-03 0 0 347.18KB 6 页 10玖币

侵权投诉

Punctured Binary Simplex Codes as LDPC codes

Massimo Battaglioni

Dept. of Information Engineering

Marche Polytechnic University

Ancona, Italy

m.battaglioni@staff.univpm.it

Giovanni Cancellieri

Dept. of Information Engineering

Marche Polytechnic University

Ancona, Italy

g.cancellieri@staff.univpm.it

Abstract—Digital data transfer can be protected by means of

suitable error correcting codes. Among the families of state-of-

the-art codes, LDPC (Low Density Parity-Check) codes have

received a great deal of attention recently, because of their

performance and ﬂexibility of operation, in wireless and mobile

radio channels, as well as in cable transmission systems. In this

paper, we present a class of rate-adaptive LDPC codes, obtained

as properly punctured simplex codes. These codes allow for the

use of an efﬁcient soft-decision decoding algorithm, provided

that a condition called row-column constraint is satisﬁed. This

condition is tested on small-length codes, and then extended

to medium-length codes. The puncturing operations we apply

do not inﬂuence the satisfaction of the row-column constraint,

assuring that a wide range of code rates can be obtained. We

can reach code rates remarkably higher than those obtainable

by the original simplex code, and the price in terms of minimum

distance turns out to be relatively small, leading to interesting

trade-offs in the resulting asymptotic coding gain.

Index Terms—Golomb rulers, LDPC codes, Minimum Dis-

tance, Simplex codes

I. INTRODUCTION

Simplex codes are duals of Hamming codes [1]. In poly-

nomial representation, for a binary ﬁnite ﬁeld, they exhibit a

parity-check matrix Hwhere a primitive binary polynomial

h(x)shifts along a diagonal trace, from left to right, by one

position each row. On the cyclic code length N, the tern

describing simplex codes is [N, k, d], where N= 2k−1

is the block length and dmin = 2k−1is the code minimum

distance. All the 2k−1non-null codewords have weight

dmin [2]. Precisely, such non-null code words represent all the

possible cyclic shifts of the same maximum-length pseudo-

random binary sequence [3]. The parity-check polynomial

h(x)has degree k, with coefﬁcients h0=hk= 1, and can be

interpreted as the generator polynomial of a Hamming code

(the dual of our code) having the same cyclic code length N.

In Fig. 1 the general form of such an Hmatrix is shown. It

exhibits Ncolumns and N−krows.

It is possible to choose a shorter code length n, with n<N,

by eliminating external rows and hence external columns. This

operation is called puncturing [4] and can be repeated as many

times as one wishes. So nbecomes a variable, whereas kdoes

not change. After selementary row-column eliminations, the

punctured code is described by the new tern [n, k, d0], with

n=N−s, and the number of rows in the new parity-check

matrix H0is reduced to r=n−k. Finally, d0is the new

minimum distance. After this construction, the rows of the

Fig. 1. General form of the parity-check matrix of (punctured) simplex codes.

Out of the main diagonal band, only 0symbols are present. Effects of s= 2

row-column eliminations, starting from the bottom right.

parity-check matrix remain all linearly independent, so that

H0still has full rank.

The code rate k

ncan be easily synthesized, leading to

a rate-adaptive coding system. It is unavoidable that the

new minimum distance d0becomes smaller and smaller, for

increasing values of s. Nevertheless, the main drawback of

simplex codes, on their cyclic length N, that is a very low code

rate, can be partially overcome. The problem of predicting

word weight distributions and new minimum distances d0for

punctured binary simplex codes has been already faced [5],

[6]. Nevertheless, a research question remains open, regarding

an efﬁcient low-complexity soft-decision decoding procedure,

able to exploit the good design characteristics of these codes.

The main contribution of the present paper is in the inter-

pretation of the parity-check matrix of simplex codes as a

sparse matrix. Owing to this, the decoding algorithms which

are suitable for Low-Density Parity-Check (LDPC) codes, can

be adopted. In this context, the conditions for satisfying row-

column constraint [7] will be investigated, in order to assure

a straightforward decoding procedure, e.g. by means of the

sum-product algorithm [8]. The availability of primitive poly-

nomials to be chosen as h(x)will be veriﬁed. Furthermore,

a circulant expansion procedure [7] in designing the ﬁnal

form of the Hmatrix will be suggested. Some simulations of

the code performance on an Additive White Gaussian Noise

(AWGN) channel will demonstrate feasibility of the proposed

solution. The arguments are organized as follows. In Section

II we provide some preliminary considerations. In Section III

we obtain some theoretical results. In Section IV some word

weight distributions are calculated, allowing to predict the

progressive performance improvement for increasing values of

arXiv:2210.03537v1 [cs.IT] 7 Oct 2022

k. In Section V we provide some numerical results, in terms

of BER curves. Finally, we draw some concluding remarks in

Section VI.

II. PRELIMINARIES

A Golomb ruler is a sequence of non-negative integers such

that every difference of two integers in the sequence is distinct.

The Hamming weight of a vector is deﬁned as the number

of non-zero symbols it contains and is simply called weight

in the following.

In this paper, we only consider binary LDPC codes. LDPC

codes are a family of linear codes characterized by parity-

check matrices having a relatively small number of non-zero

entries compared to the number of zeros. Namely, if an LDPC

H∈Fr×n

2has full rank r < n and row and column weight in

the order of log(n)and log(r), respectively, then it deﬁnes

an LDPC code with length nand dimension k=n−r,

with code rate R=k

n. If all the rows of Hhave the

same weight, we denote it as wc. The associated code is

C=c∈Fn

q|cH>=0, where >denotes transposition. The

number of codewords of weight wis denoted as A(w).

The row-column constraint in the parity-check matrix of

an LDPC code expresses the condition of not having four 1-

symbols in the vertices of a rectangular geometry, forming a

4-length closed cycle in that matrix. It is well known that soft-

decision decoding algorithms, like the sum-product algorithm,

exhibit convergence problems when working on parity-check

matrices containing the aforementioned 4-length cycles.

In the following, we consider punctured simplex codes as

LDPC codes, represented by parity-check matrices as those

in Fig. 1, described by a primitive parity-check polynomial

h(x) = 1+h1x+. . .+h2xk−1+xkof degree kand weight w,

where hiis either 0or 1. We deﬁne the vector hcontaining the

his, for i∈ {0, . . . , k}. We also deﬁne the vector pof length

w, containing {i∈ {0, . . . , k}|hi= 1}in ascending order.

In other words, pis the support of the vector containing the

coefﬁcients of the polynomial. Finally, we deﬁne the vector s

of length w−1, such that si=pi+1 −pi,i∈ {0, . . . , w −2}.

The following result holds.

Theorem 1 A necessary and sufﬁcient condition for the satis-

faction of the row-column constraint for a punctured simplex

code is that the corresponding p, derived from the primitive

parity-check polynomial h(x), is a Golomb ruler.

Proof: A4-length cycle exists in Hif and only if there

exist two pairs (i1, i2),(i3, i4)such that hi1=hi2=hi3=

hi4= 1 and i2−i1=i4−i3, being (i1, i2, i3, i4)different

one another, except that it might be i1=i4.

Each entry of pcorresponds to a non-zero coefﬁcient of

h(x). Then, if pis a Golomb ruler, by deﬁnition, there cannot

exist two pairs of different indices (j1, j2)and (j3, j4)such

that pj2−pj1=pj4−pj3. However, if pcontains pk, for some

k, then, by deﬁnition, hpk= 1. Therefore, if pis a Golomb

ruler, there cannot exist two pairs (i1, i2),(i3, i4)such that

hi1=hi2=hi3=hi4= 1 and i2−i1=i4−i3. This implies

that, if pis a Golomb ruler, Hcannot contain 4-length cycles

and therefore satisﬁes the row-column constraint.

In order to prove that this condition is necessary we need

to show that, if pis not a Golomb ruler, then Hdoes not

satisfy the row-column constraint. If pis not a Golomb ruler,

then there exist two pairs (j1, j2)and (j3, j4)such that pj2−

pj1=pj4−pj3, also implying that hpj1=hpj2=hpj3=

hpj4= 1. This is the condition of existence of a 4-length

cycle, which corresponds to the dissatisfaction of the row-

column constraint.

Now we will consider the properties emerging from an

inspection of all the binary primitive polynomials for k∈

{3,...,8}. Since they are formed by couples of reciprocal

asymmetric polynomials [2], in Table I we report only one

element for each couple. The notation adopted consists of

representing the binary expressions of any polynomial. The

number of different polynomials, on average, grows with k,

but in this very small sample it is possible to recognize various

typical well-known properties.

The weight wof primitive polynomials is always an odd

integer number, not smaller then 3. For many values of k,

primitive polynomials with weight w= 3 are present. This

is not true in few cases, say for k= 8, where the minimum

weight is 5. Nevertheless 5-weight primitive polynomials, as

what is known for kup to 10,000, are always present when

3-weight polynomials are not [9]. We are interested in ﬁxing

conditions able to assure that the row-column constraint is

satisﬁed.

III. ANALYSIS OF THE PROPERTIES OF PUNCTURED

SIMPLEX CODES

In this section we study the properties of the considered

codes, ﬁrst focusing on parity-check polynomials with weight

3, and then generalizing the obtained results.

A. Codes characterized by parity-check polynomials of weight

Although the case of a 3-weight primitive polynomial

gives only poor performance, we will investigate this case

in detail, with the purpose of understanding the mechanisms

of possible low-weight code word existence. The following

property holds.

Theorem 2 Given a primitive polynomial of weight w= 3,

the row-column constraint is always satisﬁed on a punctured

simplex code.

Proof: The proof easily follows from the fact that prim-

itive polynomials are always asymmetrical and are character-

ized by h0=hk= 1. Given this, we have

p= [0, s0, k],

where s06=k

2because of the asymmetry. Then, pis a Golomb

ruler characterized by differences s0,s1=k−s0and k,

and the parity-check matrix constructed with h(x)satisﬁes

the row-column constraint, because of Theorem 1.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

PuncturedBinarySimplexCodesasLDPCcodesMassimoBattaglioniDept.ofInformationEngineeringMarchePolytechnicUniversityAncona,Italym.battaglioni@staff.univpm.itGiovanniCancellieriDept.ofInformationEngineeringMarchePolytechnicUniversityAncona,Italyg.cancellieri@staff.univpm.itAbstractDigitaldatatransfercan...

展开>> 收起<<

Punctured Binary Simplex Codes as LDPC codes Massimo Battaglioni Dept. of Information Engineering.pdf

共6页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Punctured Binary Simplex Codes as LDPC codes Massimo Battaglioni Dept. of Information Engineering

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: