INT J COMPUT COMMUN, ISSN 1841-9836
Vol.7 (2012), No. 2 (June), pp. 388-395

A Reliability Level List based SDD Algorithm for Binary Cyclic
Block Codes

B. Yamuna, T.R. Padmanabhan

B.Yamuna
Assistant Professor,Dept of ECE
Amrita Vishwa Vidyapeetham,
Amrita School of Engineering
Amrita Nagar, Coimbatore. 641 112
Tamil Nadu, India
E-mail: b_yamuna@cb.amrita.edu

Dr. T.R.Padmanabhan
Professor Emeritus, Dept of IT
Amrita Vishwa Vidyapeetham,
Amrita School of Engineering
E-mail: trp@amrita.edu

Abstract: Soft decision decoding (SDD) provides a better coding gain by
making use of the unquantized channel output. In this paper we introduce the
concept of a Reliability Level List (RLL); based on the RLL a new SDD algo-
rithm for Binary Phase Shift Keying (BPSK) based binary cyclic block codes
is proposed. The algorithm guarantees to extract the most reliable codeword
in an iterative manner. The formation of the RLL involves a search for the
next possible entry into the RLL based on the error probability which is a re-
flection of the reliability values of the bits of the received word obtained from
the channel. The procedure for the formation of RLL which is the central idea
of the paper is given as a structured algorithm.
Keywords: cyclic block codes, reliability based decoding, soft decision decod-
ing, probability of error.

1 Introduction

Soft decision decoding (SDD) algorithms in general focus on the extraction of the codeword
from the received word by making use of the reliability information available at the channel
output which is otherwise discarded in hard decision decoding. SDD algorithms have increased
complexity compared to hard decision decoding but they trade off complexity for better error
performance.

The idea of exploiting the real channel output to the maximum possible extent instead of
quantizing it to 0’s and 1’s as with hard decision decoding has been the essence of SDD vis-â-vis
binary cyclic block codes. Different SDD algorithms have been proposed in the recent years-each
with its own trade off between complexity and error performance[1- 3].

The reliability based SDD algorithms aim at decoding a received word which is more reliable
even under low signal-to-noise ratio (SNR) conditions. Researchers are focusing on making the
best use of the channel output and improving decoding reliability. In these algorithms the
channel output is used to quantify reliability values of the bits of the received word. The bits are
processed with respect to their reliability values. They can be based on processing the bits from
the least reliable end as with Chase decoding algorithms and Generalized-minimum distance
(GMD) decoding algorithms [4], [5] or they can be based on processing from the most reliable

Copyright c⃝ 2006-2012 by CCC Publications



A Reliability Level List based SDD Algorithm for Binary Cyclic Block Codes 389

end as with Ordered Statistics Decoding algorithms[6].
A SDD algorithm is evolved in this paper. The algorithm uses the channel output reliability

in the true sense. The significance of the work is in the fact that the target codeword identified
through the algorithm here is the best that reliability based SDD algorithm can lead to.

The method involves searching in a space of 2n words for the most reliable codeword. But
the extent of actual search is confined to a much shorter range as brought out in the paper. The
focus of the paper is two-fold: (1) Proving that the codeword extracted is the best possible one
from a soft decision point of view and (2) giving a structured algorithm for the extraction of the
codeword.

2 Preliminaries of the RLL based SDD Algorithm

The problem of SDD is one of starting with the received word and identifying a codeword
which will be the most reliable one; this codeword is called the ’target codeword’ here. The
process essentially amounts to arranging all the possible 2n binary bit sequences in the order of
increasing reliability and picking the first codeword from it. The sequence so arranged is called
the Reliability Level List (RLL) here. Hence RLL represents the search sequence to be followed
to find the most reliable codeword.

For an n bit sequence let the pair {(bi, mi)}, 0 ≤ i ≤ n represent the sets of the bit
values and the corresponding reliability magnitudes. Each bit of hard decision has an associated
probability of error given as

∫ ∞
mi

1√
2π
e−

x2

2 dx.

Let Q(mi
σ
)=

∫ ∞
mi

1√
2π
e−

x2

2 dx, σ being the noise variance. Arrange the set {Q(mi
σ

)} in de-
scending order of magnitudes and assign integer values k to them such that k =1 for the bit with
the largest value of Q(mi

σ
); let q[1] represent this Q(m

σ
) value. Similarly k = 2 for the next one

with q[2] representing the corresponding Q( m
σ

) value and so on until k = n for the bit with the
smallest value of Q( mi

σ
). Let {q[k]} be the rearranged set of numbers and {p[k]} = {1 − q[k]}.

With an (n,k) code all the 2k possible codewords are included in the total space of 2n

words. All these codewords appear in the RLL each with its own associated probability of being
the target codeword; the very first codeword to appear in the list being the most reliable of the
codewords is the target codeword; those further down the RLL being less reliable need not be
examined. The first few entries in RLL as defined above can be seen to be as given below:

• The topmost entry is the term
∏15

k=1 p[k] having the largest magnitude. This represents
the received word itself. i.e., none of the bits is in error.

• The next entry in RLL is the product q[1]
∏15

k=2 p[k] having the next higher magnitude.
This represents the received word with the least reliable bit with k =1 being in error.
Hence the received word with the least reliable bit flipped is examined and if found to be
a codeword it is the target codeword and the search stops. If it is not a codeword then
the subsequent entry in RLL has to be made and the process of examining the entry for
identification of target codeword is to be continued. The process is thus repeated until
target codeword is identified. The third and fourth entries are given below for clarity.

• The third entry in RLL is the term q[2]p[1]
∏15

k=3 p[k]

• The fourth entry in RLL is either q[3]p[2]p[1]
∏15

k=4 p[k] or p[3]q[2]q[1]
∏15

k=4 p[k] based on
whichever candidate has the higher magnitude. In general the position of a word in RLL
is decided by the magnitude of the corresponding product∏

ki

p[ki]
∏
kj

q[kj] (1)



390 B. Yamuna, T.R. Padmanabhan

where ki and kj represent the set of k values for which the p[ki] and q[kj] values respectively
appear in the product. This is the crux of selecting the next entry in to the RLL at every stage.
Withs[k ] = q[k]

p[k]
define

f =

∏
kj
q[kj]∏

ki
p[ki]

(2)

Using f the product
∏n

τ=1 P [τ]×f can be used in place of the product in (1) above. This directly
leads to the following lemma.
Lemma 1:
Let v represent the rank of an entry in RLL and fv the corresponding f value as defined in equation
(2). Then the vth entry in RLL is such that fv−1 ≥ fv ≥ fv+1 for 0 ≤ v ≤ n

The above inequality means that the problem of identifying the rank of an entry in the
RLL is the same as computing the fv′s and arranging them in descending order of magnitudes.
Since log fv is a monotonically increasing function of f, the inequality implies log fv−1 ≥ logfv
≥ log fv+1 for 0 ≤ v ≤ n.
If an entry in RLL is known its log fv is known. The problem of deciding the very next entry
can be looked upon as the problem of identifying a set of log s[k] such that the corresponding Σ
log s[k] satisfies the following two conditions

1. It should be smaller than the Σlog s[k] for the present entry.

2. It should be the largest in magnitude amongst the set yet to be entered in the RLL.

With W =Σ log s[k], an entry with rank v in RLL is characterized by its Wv. With this the
above result can be formalized as a theorem:
Theorem 1:
For any v ∈ {0, 2n−1} the corresponding entry in RLL has a Wv such that wv−1 ≥ wv ≥ wv+1
Log s[k] being a negative quantity, W =Σlog s[k] is also a negative quantity. It is more convenient
to work with log ( 1

s[k]
) = (-log s[k]) and the corresponding sum M = -Σ log s[k]. With this,

Theorem 1 implies Lemma 2 below which is more convenient to work with.
Lemma 2:
For any v ∈ {0, 2n−1 } the corresponding entry in RLL has a Mv such that Mv−1 ≤ Mv ≤ Mv+1

3 Procedure for Forming the RLL

The procedure involves forming sequences of n bit binary numbers which would be the entries
in the RLL. Let v denote the rank of an entry in the list with v ranging from 0 to 2n. The step
by step procedure for making the entries in the RLL is follows.

1. M0, M1, M2, where M0 =0,M1 = - log s[1], M2 = - log s[2] are formed as explained earlier
in section 2 and the corresponding binary sequences designated N0, N1, N2 are entered in
the RLL.

2. Define a ’pending list’ - PL as the collection of all contenders for the next entry to the
RLL.

3. The entries in the PL are characterized by the following.

(a) Each entry is a collection of indices.

(b) Each entry has an associated characteristic magnitude - M.



A Reliability Level List based SDD Algorithm for Binary Cyclic Block Codes 391

4. Once the PL is fully known, the next entry to the RLL can be decided by comparing the
M values for each entry in the PL. It also implies that the left over elements in the PL will
also be members for the PL for the subsequent entry in the RLL.

5. Once an entry to the RLL is decided, the PL for the next entry to the RLL is formed
through the following steps.

(a) All the entries left over after the previous entry to the RLL are also to be in the new
PL.

(b) Additional sets are to be added to the new PL depending on the present entry to the
RLL. This essentially amounts to scanning the indices in the set for the present entry
and altering them. A perusal of the set of indices shows that the additional element
sets can be formed as follows:

i. If the least index K1 for the set is not 1 add 1 to the index set.
ii. For every index Xi in the set if Xi+1 < Xi+1 replace Xi with Xi+1. This amounts

to adding a set to the PL where the contribution to M by Xi is increased by the
least possible amount in the neighborhood of Xi.

The procedure to form the RLL as a sequence of 2n binary numbers explained above can be cast
as structured algorithm. The list of notations used in the algorithm is given below:

• K: reliability index assigned to the bits of the received word.

• Nv : binary number in RLL with rank v.

• s[k] = q[k]
1−q[k]

• n : block length of the codeword

• PL : Pending list after updating

• Pu : pending list before updating

• Ti : ith set in PL

• Jmax :total number of Ti′s in PL

• βi: number of elements in Ti

• F : flag

• Ui, µ, ∆: Temporary symbols used for Ti′s, Ui , and Jmax respectively

4 RLL based SDD Algorithm

1. Input: {-log s[k]}, n.

2. Output: Sequential entries in RLL

3. Initial Condition: N0 = {0}, N1 = {1}, N2 = {2}, PL = {T1, T2} where T1 = {3}, T2 =
{1, 2},Jmax = 2, F = 0.

4. Do For v=3 to 2n



392 B. Yamuna, T.R. Padmanabhan

5. Do For i=1 to Jmax
Compute Mvi = −

∑βi
α=1 log(s[Xα])

EndDo i

6. Mmin = min{ Mvi for i = 1 to Jmax}

7. Let im = the i for which Mvi is minimum

8. Form a binary sequence Nv whose 1 bits are decided by the indices in the set Tim

9. βv = βim

10. Do for i=1 to Jmax
If(i ̸= im) Ui = Ti
EndDo i
(Removing Tim from the pending list and reassigning the Ti’s to the Ui’s.)

11. Pu = {0}

12. Do for i = i to im−1
Pu = { Pu :Ui}
EndDo i

13. Do for i = im to Jmax

(a) Ui = Ui+1
(b) Pu = { Pu :Ui}

(c) βi = βi+1

EndDo i

14. In Nv (Updating the pending list by forming candidate entries; processing done with present
entry)

15. Do for d = 1 to n

(a) If K1 ̸= 1, (If LSB of Nv is 0 add 1 to the present entry)
{

i. µ = { Nv :1}
ii. if µ is not in Pu ,
iii. Ui = µ for i = Jmax
iv. ∆ = Jmax
v. βJmax = βJmax + 1
vi. F = 1

}

(b) If Kd +1 < Kd+1
{
If F =1
{

i. Form µ with Kd replaced by Kd +1 in Nv
ii. If µ is not in Pu ,



A Reliability Level List based SDD Algorithm for Binary Cyclic Block Codes 393

iii. U∆+1 = µ
iv. β∆+1 = βv
}
Else
{

15.2.5 Form µ with Kd replaced by Kd +1 in Nv
15.2.6 If µ is not in Pu
15.2.7 U∆ = µ
15.2.8 β∆ = βJmax

}

16. Increment ∆
}

17. Jmax = Jmax +1

18. EndDo d

19. PL = Pu for i =1 to ∆ (Pending list updated)

20. F = 0.

21. EndDo v

5 Example

Extensive simulation with a variety of binary cyclic block codes like (15, 7), (31, 16),
and (127, 64) have been carried out; in each case a few thousand transmissions over an AWGN
channel was done for different values of σ and the erroneous received words decoded using the
proposed algorithm. In all the cases the resultant target codeword was found to be the most
reliable one. Details of a representative set are discussed briefly here.

A (15, 7) binary cyclic block code with dmin = 5 and t =⌊ dmin/2 ⌋ = 2 is considered.
The message 030h has been encoded as 304eh and transmitted over an AWGN channel with σ=
0.8. The received word is 78cch. There are 4 errors at bit positions 1, 7, 11, 14. With the input
as the set {-log s[k]}, n = 15 and the Initial Condition as:N0 = {0} N1 = {1} , N2 = {2}, PL =
{T1, T2} where T1 = {3}, T2= {1, 2},Jmax = 2, F = 0, following the steps of the algorithm the
RLL was formed. A representative segment of the RLL is given in Table 1. The table gives the
rank v, k value, Mmin , and the contents of Ti with the corresponding Mvi (both separated by
a hyphen in the table).

As seen in Table 1 in each row the specific Ti in italics has the minimum value of Mvi and
forms the candidate identified for the next entry. Further in each row the entries in bold repre-
sent the updated candidates that are formed by applying the rules in row 15 in the algorithm
given above in section 4. For example considering the row with rank 82, the entry T36= {2,3,6,7
- 0.977} - with k=2, k = 3, k = 6, k = 7 as 1′s and Σ log s[k] as 0.977 - is the next entry with
rank as 83 ; and this is the one with minimum of Mvi . The entries in the same row with rank 82,
namely T38 = {1,4,6,7 - 1.198} and T39 = {1,3,6,8 - 1.4992}are the ones formed on applying
the rules in rows 15.1 and 15.2.1 of the algorithm given in section 4 respectively.



394 B. Yamuna, T.R. Padmanabhan

Table 1: Partial RLL
Rank
v

K M min Details of T i‘s in the Updated pending list PL

1 1 0.0832

2 2 0.0957 T1= {3 - 0.1223 }, T2= {1,2 - 0.1789}

3 3 0.1223 PL= { T1, T2, T3}; T1= {1,2 -0.1789 }, T2= {1,3
-0.2055}, T3= {4,-0.3558}

4 1,2 0.1789 T1= {1,3 - 0.2055 }, T2= {4 - 0.3558}

5 1,3 0.2055 T1= {4 - 0.3558}, T2= {2,3 - 0.218}, T3= {1,4
- 0.439}

. . . .

. . . .
82 1,3,6,7 0.9645 T1= {1,8 - 0.9978}, T2= {2,8 - 1.0103}, T3=

{3,8 - 1.0369}, T4= {1,2,8 - 1.0935}, T5= {1,3,8
- 1.1201}, T6= {2,3,8 - 1.1326}, T7= {1,2,3,8
- 1.2158}, T8= {4,8 - 1.2704}, T9= {5,8 -
1.2727}, T10= {6,8 - 1.2937}, T11= {1,4,8 -
1.3536}, T12= {1,5,8 - 1.3559}, T13= {2,4,8 -
1.3661}, T14= {2,5,8 - 1.3684}, T15= {1,6,8 -
1.3769}, T16= {2,6,8 - 1.3894}, T17= {3,4,8
- 1.3927}, T18= {4,5,6 - 1.093}, T19= {4,5,7
- 1.0938},T20= {3,5,8 -1.395}, T21= {4,6,7 -
1.1148}, T22= {3,6,8 - 1.416}, T23= {1,2,4,8 -
1.4493}, T24= {1,2,5,8 - 1.4516}, T25= {1,2,3,4,5
- 1.0151}, T26= {1,2,6,8 - 1.4726}, T27= {1,9 -
1.0262}, T28= {10 - 1.0421}, T29= {1,2,3,4,6 -
1.0361}, T30= {1,2,3,4,7 - 1.0369}, T31= {2,3,4,8
- 1.4884}, T32= {1,2,3,5,6 - 1.0384}, T33=
{2,4,5,6 - 1.1887}, T34= {1,2,3,5,7 - 1.0392},
T35= {2,4,5,7 - 1.1895}, T36= {2,3,6,7 - 0.977},
T37= {2,3,5,8 - 1.4907}, T38= {1,4,6,7 - 1.198
}, T39= {1,3,6,8 - 1.4992 }

83 2,3,6,7 0.977 T1= {1,8 - 0.9978}, T2= {2,8 - 1.0103},
. . . . . . . . . . . . . . . .T37= {1,4,6,7 - 1.198 }, T38=
{1,3,6,8 - 1.4992 },T39={1,2,3,6,7 - 1.0602},
T40={2,4,6,7 - 1.2105}, T41={2,3,6,8 -
1.5117}.



A Reliability Level List based SDD Algorithm for Binary Cyclic Block Codes 395

With each such entry to the RLL the corresponding candidate word is formed by com-
plementing the bits indicated by the entry. The candidate word is examined to check if it is a
codeword; if yes it is the desired target codeword. Once the target codeword is identified the
process of filling the RLL can be discontinued since any codeword found below this in the RLL
is less reliable. For the specific case here the target code word is obtained at the rank of 83 with
errors at bits 7, 1, 11, and 14 with the corresponding K values as 2, 3, 6, and 7 respectively.

6 Conclusion

A structured, iterative, and reliability based Soft Decision Decoding algorithm is proposed.
The algorithm uses the reliability value of the received word as a soft metric and outputs the
desired target codeword through an ordered search in the 2n word space. The algorithm identifies
an entry in the RLL such that the corresponding word is the most reliable yet. For each entry in
the RLL the corresponding word formed has to be checked to see if it is a code word and if so it
is the desired target codeword. The proposed algorithm guarantees to return the best in terms of
reliability because of the very fact that any other codeword found below the identified one will
be less reliable. The structured algorithm can be easily coded and used for decoding any (n,k)
binary cyclic block code.

Bibliography

[1] Wenyi Jin and Marc.P.C.Fossorier,Fellow,IEEE, Reliability-Based Soft-Decision Decoding
with Multiple Biases , IEEE Trans. Inform. Theory, Vol. 53, pp. 105-120, Jan. 2007

[2] Ye Liu, Member, IEEE, Shu Lin, Fellow, IEEE, and Marc.P.C.Fossorier,Fellow,IEEE, MAP
algorithms for Decoding linear block codes based on sectionalized Trellis diagrams, IEEE
Trans. Communications, Vol. 48, pp. 577-587, Apr. 2000

[3] Yuansheng Tang, Member, IEEE, San Ling and Fang - WeiFu, On the Reliability - Based
Soft - Decision Decoding Algorithms for Binary Linear Block Codes, IEEE Trans. Inform.
Theory, Vol. 52, pp. 328-335, Jan. 2006

[4] David Chase, Member, IEEE, A Class of Algorithms for Decoding Block Codes With Channel
Measurement Information, IEEE Trans. Inform. Theory, Vol. IT-18, pp.170-182, Jan 1972

[5] G. D. Forney, Jr., Generalized minimum distance decoding, IEEE Trans. Inform. Theory,
Vol. IT-12, pp. 125-131, Apr. 1966

[6] Marc P. C. Fossorier, Member, IEEE, and Shu Lin, Fellow, IEEE, Soft-Decision Decoding of
Linear Block Codes based on Ordered Statistics,IEEE Trans. Inform. Theory, Vol. 41, pp.
1379-96, Sep 1995