IEEE TRANSACTIONS ON COMMUNICATIONS

1

Repeat-Accumulate Signal Codes

arXiv:1802.01133v2 [] 6 Feb 2018

Manato Takai, Student Member, IEEE and Koji Ishibashi, Member, IEEE

Abstract

We propose a new state-constrained signal code, namely repeat-accumulate signal code (RASC).
The original state-constrained signal code directly encodes modulation signals by signal processing
filters, the filter coefficients of which are constrained over Eisenstein rings. Although the performance
of signal codes is defined by signal filters, optimum filters were found by brute-force search in terms
of symbol error rate (SER) in the literature because the asymptotic behavior with different filters has
not been investigated. We introduce Monte Carlo density evolution (MC-DE) to analyze the asymptotic
behavior of RASCs. Based on our analysis by MC-DE, the optimum filters can be efficiently found
for given parameters of the encoder. Numerical results show the difference between the noise threshold
and the Shannon limit is within 0.8 dB. We also introduce a low-complexity decoding algorithm. BCJR
and fast Fourier transform-based belief propagation (FFT-BP) increase exponentially as the number of
output constellations increase. The extended min-sum (EMS) decoder under constraint over Eisenstein
rings is established to overcome this problem. Simulation results show the EMS decoder can reduce
the computational complexity to less than 25% of that of BCJR and FFT-BP without a significant
performance loss, which would be greater than approximately 1 dB.

I. I NTRODUCTION
Capacity approaching codes, such as low-density parity check (LDPC) codes and turbo codes,
provide significant coding gains [1], [2], [3]. Based on theoretical analysis, the noise thresholds

M. Takai and K. Ishibashi are with Advanced Wireless & Communication Research Center (AWCC), University of ElectroCommunications, 1-5-1 Chofugaoka, Chofu-shi, Tokyo 182-8585, Japan e-mail: {manato, koji}@ieee.org

February 7, 2018

DRAFT

2

IEEE TRANSACTIONS ON COMMUNICATIONS

of these codes, which are the maximum decodable noise variances, are close to the Shannon limit.
Moreover, simulation results show that these codes exhibit high coding gain over the additive
white Gaussian noise (AWGN) channel when binary phase shift keying (BPSK) is used [4], [5].
However, in practice, it is difficult to approach the Shannon capacity because the correlation
among unreliable coded bits degrades the decoding performance when high-order modulation is
used. Coded modulation is an effective technique for enhancing the coding gain with high-order
modulation because this technique enables the Hamming distances of the linear codes and the
Euclidean distances of the modulation to be designed in an integrated manner [6], [7]. In order
to achieve a high transmission rate, the computational complexity encountered in designing these
two distances is impractical because of the enormous number of constellation points involved.
Lattice codes are structured codes for AWGN channels, which have gained a great deal of
attention since Erez and Zamir proved that lattice codes achieve the Shannon capacity [8]. The
advantage of lattice codes is that linear codes over a Hamming space can easily be transformed to
Euclidean space by algebraic construction [9]. The use of a lifting scheme, such as construction
A or construction D, combined with powerful linear codes has shown excellent performance.
For instance, in [10], LDPC codes were used to design construction D lattices, and the resulting
performance was within 3 dB of the Shannon limit. In [11], lattice construction using turbo
codes and a decoding algorithm was proposed. Turbo lattices achieve a performance of within
approximately 1.25 dB of the Shannon capacity. Although these codes can directly integrate the
coded sequence with modulation signals, it is impractical to implement lattice codes because
the constellation of lattice codes expands infinitely over the signal space. Thus, the transmitted
power could be unbounded. Furthermore, due to the enormous number of constellation points,
both encoding and decoding involve significant computational complexity.
Recently, signal codes were proposed as a feasible lattice-coded modulation technique. The
entire encoding process consists of simple signal convolution via infinite impulse response (IIR)
and/or finite impulse response (FIR) filters. In signal codes, filter coefficients are the most
DRAFT

February 7, 2018

SUBMITTED PAPER

3

important parameters for coding gain because the coefficients define Euclidean distances among
generated codewords. The authors herein show that the absolute values of filter coefficients
must be close to one in order to obtain high coding gain [12]. This implies that the transmission
power exponentially increases with codeword length, and shaping techniques such as TomlinsonHarashima precoding (THP) is necessary to meet average power constraint in practice. Although
THP can tailor the transmission power, the number of possible constellation points becomes infinite. This fact results in a exponential decoding complexity, and well-known powerful decoding
algorithms such as BCJR algorithm cannot be utilized [13]. Therefore, in [12], a list decoder
is used, and the decoding performance is within 2 dB of the Shannon limit, at which the frame
error rate (FER) is equal to 10−3 . However, list decoding is sub-optimal and is inferior to BCJR
algorithm.
Mitran and Ochiai proposed state-constrained signal codes called turbo signal codes to overcome the explosion of the decoding complexity [14]. In state-constrained signal codes, shaping
coefficients are chosen over Eisenstein rings. Since rings are closed under addition and multiplication, the output signals are also constrained over Eisenstein rings, and the possible constellation
points become finite. This additional constraint enables the decoder to use BCJR algorithm.
This additional constraint enables the decoder to use the BCJR algorithm, and the resulting
performance is within 0.8 dB of the Shannon limit, at which the symbol error rate (SER) is
at 10−4 . Although the decoding complexity has been relaxed by Eisenstein rings, turbo signal
codes still suffer from a remarkable increase in the number of possible states of filters when
higher-order modulation is used as input because the number of states increases exponentially as
the order of the modulation increases. This prevents the decoder from using the BCJR algorithm.
Moreover, the fundamental code properties of signal codes, such as the decoding threshold, have
not yet been investigated. Therefore, we resort to a brute-force search of the filter coefficients
in order to obtain higher coding gain [14].
In this paper, in order to address the inherent problems of conventional turbo signal codes, we
February 7, 2018

DRAFT

4

IEEE TRANSACTIONS ON COMMUNICATIONS

propose novel state-constrained signal codes, called repeat-accumulate signal codes (RASCs).
RASCs are based on repeat-accumulate (RA) codes [15]. The proposed RASCs are composed
of a repeater, an interleaver, and one tap IIR filter, i.e., an accumulator. Here, the codewords are
restricted not only by Eisenstein rings but also by parity check constraints. Although the parity
check constraints require density evolution (DE) in order to analyze the noise threshold of the
RASCs, regular DE cannot be used because tracking true densities is impractically complex.
Hence, we introduce MC-DE [16] for revealing the asymptotic behavior of the RASCs. Thus,
the condition for the optimum filter is also studied via MC-DE. Moreover, we introduce a
low-complexity decoding algorithm based on the EMS algorithm. The proposed algorithm is
modified to decode the codes over Eisenstein rings. The simulation results reveal that the modified
EMS can reduce the complexity to a quarter of that of the BCJR algorithm without significant
performance loss. In summary, the contributions of the present study are as follows:

•

Thresholds with several important parameters of RASCs, such as the filter, the number of
basis of rings, the column weight, and the input constellation size, are determined via MCDE. By carefully choosing the parameters, the Shannon capacity is approached to within
approximately 0.8 dB.

•

A new input constraint is introduced in order to increase the transmission rate. In conventional turbo signal codes, the input signals were constrained by quadrature amplitude
modulation (QAM), which is a subset of Eisenstein rings, because providing redundancy
in terms of constellation size can be used to improve the error performance [14]. However,
our analysis via MC-DE indicates that the thresholds when the input signals are constrained
over Eisenstein rings are slightly better than those when the input signals are constrained
by QAM.

•

We introduce a modified EMS algorithm for state-constrained signal codes in order to reduce
the decoding complexity [17]. The key concept of EMS is to extract only the highly reliable

DRAFT

February 7, 2018

SUBMITTED PAPER

5

elements of the message vector in order to reduce the size of the exchanged message vector.
As a result, the decoding complexity dramatically decreases because it does not depend on
the number of output constellation points but rather on the size of the truncated message
vectors. Simulation results show that the performance loss by message truncation is only
approximately 1 dB with a computational complexity of less than a quarter of that of the
BCJR or SP algorithm.
The remainder of this paper is organized as follows. The basics of the signal codes, such
as the system model, channel model, and the definition of Eisenstein rings, are explained in
Section II. In Section III, we propose the encoding and decoding structure of RASCs. Section
IV shows the optimum filters and their decoding thresholds as calculated by MC-DE. In Section
V, numerical results of RASCs obtained using FFT-BP and EMS decoders are presented, and
the decoding performances of RASCs and turbo signal codes are compared. Finally, Section VI
concludes the paper.

II. BASICS OF S IGNAL C ODES
A. System Model

Figure 1 shows a system model of general signal codes. Input complex signals s = s1, s2, · · · , sNs ∈
CNs are directly encoded by a signal encoder, where Ns is the number of input signals. We now
assume L 2 -QAM for the input signals, and its constellation is defined as follows:

Q L = v I + jv Q : v I , v Q ∈ {0, 1, · · · , L − 1} .

(1)

This implies that the input signals are defined over the residue class of a Gaussian integer,
Z L [ j] = Z[ j]/LZ[ j].

The encoder maps input signals to coded signals x = x1, x2, · · · , xNc ∈ CNc via the generator
matrix G ∈ CNc ×Ns whose elements correspond to filter coefficients, where Nc is the number
of output signals. To meet average power constraint, shaping operation should be performed in
February 7, 2018

DRAFT

6

IEEE TRANSACTIONS ON COMMUNICATIONS

Signal enc.

s

Modulation

x

x = G(s + b)
Channel
s′
Demodulation

Fig. 1.

Signal dec.

y

System model of the signal codes

the encoding process. A shaping vector b ∈ CNc restricts the amplitude of encoded signals xi ,
i ∈ {1, · · · , Nc } into a desired shaping region. In this subsection, THP is assumed as the shaping
operation. The THP aims to restrict the real and imaginary part of the output constellation into
(0, L], then the shaping operation is
xt = st +

NF
Õ

gk (st−k + bt−k ) + bt

(2)

k=1

where NF is the number of filter taps, and bt are chosen as follows:
$

bt

N

F
Õ
1
= −2L
st +
gk (st−k + bt−k )
2L
k=1

!%
.

(3)

Thus the received signals over the AWGN channel can be written by,
y = x + z = G(s + b) + z,

(4)


where the distribution of the elements of noise vector z = z1, z2, · · · , zNc ∈ CNc follows i.i.d.
(independent and identically distributed) circular symmetric zero-mean AWGN with variance
σ2.
DRAFT

February 7, 2018

SUBMITTED PAPER

7

B. Turbo signal codes over Eisenstein rings
As described above, turbo signal codes introduce the constraint based on Eisenstein rings to
control the number of output constellation points. Thus, the encoded signals of turbo signal
codes are constrained by
h

ZL e

j 2Nπ
bv

i

=

( N −1
bv

Õ



viI + jviQ e

j 2Niπ
bv

)
: viI , viQ ∈ {0, 1, · · · , L − 1} ,

(5)

i=0

where Nbv represents the number of basis of Eisenstein rings as positive integer and, v I and v Q
are also chosen as integer. Then, the tth coded signal of turbo signal codes is given by
xt =

NF
Õ

fk ut−k + f0 st +

k=1

ut = st +

NF
Õ

!
gk ut−k + bt ,

(6)

k=1
NF
Õ

gk xt−k + bt

(7)

k=1

where gk and fk respectively indicate feedback and feedforward filter coefficients constrained
h π i
j
over Eisenstein rings Z L e 2Nbv , ut−k represent the signal held in the k-th memory of the
h π i
j
encoder. All gk , fk , and bt are chosen over Z L e 2Nbv so that the encoded signals are constrained
h π i
j
over Z L e 2Nbv since rings are closed under addition and multiplication. The set of the elements
h π i
j
of Z L e 2Nbv is defined as C (L, Nbv ), and the cardinality of C (L, Nbv ) is obtained by
|C (L, Nbv )| = L 2Nbv .

(8)

For short hand notation, the index of feedback filters FB is defined as follows:
FB =

NF NÕ
bv −1 
Õ


viI × L 2i+( j−1)∗2Nbv + viQ × L 2i+1+( j−1)∗2Nbv .

(9)

j=1 i=0

The index of feedforward filters FF is expressed in the same manner as the FB. Hence,
FF =

NF NÕ
bv −1 
Õ


viI × L 2i+ j∗2Nbv + viQ × L 2i+1+ j∗2Nbv .

(10)

j=0 i=0
February 7, 2018

DRAFT

8

IEEE TRANSACTIONS ON COMMUNICATIONS

III. R EPEAT-ACCUMULATE S IGNAL C ODES
As shown in the previous section, at least three tap filter coefficients are required to construct
turbo signal codes, namely, the tap coefficients of the feedforward filters, f0 and f1 , and a tap
coefficient of the feedback filter, g1 . It is difficult for turbo signal codes to analyze the decoding
performance and to design the filter coefficients because the search space of the filter coefficients
has a minimum of L 6Nbv candidates. Therefore, RASCs are proposed in order to reduce the search
space to L 2Nbv because our encoder has only one tap filter coefficient.

A. Encoding Structure
1) Encoder: The encoder of the RASC is shown in Fig. 2. In this paper, non-systematic
RASC is assumed. The figure shows that the encoder consists of the same components as RA

codes. The output signal from the q-times repetition encoder is c = c1, c2, · · · , cqNs , and the


0
output signal from the interleaver is c 0 = c10 , c20 , · · · , cqN
, both of which are constrained over
s
the same rings as the input signals s. For instance, when the input signals are L 2 -QAM, c and c 0
become (Z L [ j])Nc , where Nc = qNs since non-systematic RASC is assumed. The accumulator
of the RASC is slightly different from that of the binary RA because the accumulator consists
of a filter and a shaping operation. The tth output signal from the encoder is given by

xt = − ct0 + g1 xt−1 + bt .

(11)

The resulting codes satisfy the following parity check equation:
xt + ct0 + g1 xt−1 = 0

h π i
j
mod Z L e 2Nbv .

(12)

Then, the RASC can be decoded by the SP algorithm since the parity check matrix can be
defined based on (12). However, turbo signal codes with the useful filter coefficients do not
satisfy the parity check equations. The proof of the filter of the turbo signal codes is presented
in Appendix A.
DRAFT

February 7, 2018

SUBMITTED PAPER

9

b
s

c
q-repetition

Symbol
interleaver

c′

xt−1

-1

x

g1

Fig. 2.

Encoder of the non-systematic RASC

2) Transmission Power: Figure 3 illustrates several signal constellations constrained by Eisenstein rings. DC shift operation works toward minimizing the transmitted power. In this case, the
averaged transmission power is given by [14]:
h

E |x|

2

i


Nbv L 2 − 1
=
.
6

(13)

3) Mapping Space of Filters: As shown in Fig. 3, the number of signal points appears to
increase as L or Nbv increases. Moreover, as shown in Figs. 3-(b) and 3-(c), the number of signal
points, defined as C̃ (L, Nbv ) , is less than the cardinality |C (L, Nbv )|. The reason for this is that
some points over C̃ (L, Nbv ) degenerate into one point over C̃ (L, Nbv ) for Nbv ≥ 3 because of
ring constraint [14].
Notably, the decoding performance of state-constrained signal codes depends on the mapping
space of the filters. Figure 4 shows four examples of mapping spaces of various filters at L = 2
and Nbv = 2. The mapping space of FB = 11 (Fig. 4-(c)) has the same constellation as Fig.
3-(a). However, the mapping spaces of FB = 3 (Fig. 4-(a)), FB = 5 (Fig. 4-(b)), and FB = 15
(Fig. 4-(d)) are a subset of C̃ (L, Nbv ). In these cases, filtered signal points are degenerated into
a few points, which implies that these filters lead to catastrophic codes because degenerated
signals cannot be correctly recovered from received signals. Therefore, bijective characteristics
are a necessary condition when choosing filters.
February 7, 2018

DRAFT

10

IEEE TRANSACTIONS ON COMMUNICATIONS

(a) C̃(2, 2)
Fig. 3.

(c) C̃(2, 4)

(d) C̃(3, 2)

All possible constellation points at the output of the RASC encoder with C̃(L, Nbv ).

(a) FB=3
Fig. 4.

(b) C̃(2, 3)

(b) FB=5

(c) FB=11

(d) FB=15

Mapping spaces of four filters for C̃(2, 2).

4) Variable Rate with Variable Input Constraint: In the turbo signal code, the achievable rate is
log2 L 2 because the input signals are constrained over Z L [ j] (i.e., L 2 -QAM). Therefore, L must be
increased in order to achieve a higher rate, but large L causes high decoding complexity because
the number of states is L 2Nbv . In this paper, we propose high rate signal codes while keeping the
decoding complexity low. As described above, the cardinality of C̃ (L, Nbv ) is identical to that
of C (L, Nbv ) if and only if Nbv = 2. Then, codewords are one-to-one mapped into a complex
plane while the number of output states is maintained. We exploit the property whereby the


input signals are chosen over Z L e jπ/4 for higher rates with the same complexity.
DRAFT

February 7, 2018

SUBMITTED PAPER

11

Then, the transmission rate of the non-systematic RASC is given by

Rc =



log2 L 2





q









 log2 L 4


 q


if s ∈ (Z L [ j])Ns
(14)
 
  Ns
if s ∈ Z L e jπ/4

B. Decoding Structure
In this subsection, two decoding algorithms, namely FFT-BP and EMS, are introduced for
the RASC. These algorithms were originally proposed for the purpose of decoding non-binary
LDPC defined over a Galois field with low computational complexity. In this paper, we modify
these decoding algorithms for use with the RASC defined over Eisenstein rings.
1) FFT-BP Algorithm: The decoding complexity of the BCJR for the state-constrained signal

codes is O L 4Nbv , because the number of states in the trellis diagram is given by L 2Nbv .
Therefore, a low-complexity decoding algorithm is required because it is difficult to decode
when L and Nbv become quite large. Thus, FFT-BP is introduced for the RASC. The complexity

of FFT-BP is reduced as O L 2Nbv log2 L 2Nbv .
The exchanged message is defined as the vector of the log-likelihood ratio (LLR), the length
of which is L 2Nbv , similar to non-binary LDPC codes. At first, notation of FFT-BP algorithm is
shown.
Notations: In a m × n parity matrix H, a set of non-zero elements of the row index at n and
a set of non-zero elements of the column index at m are defined as M(n) B {n | Hmn , 0}, and
N (m) B {m | Hmn , 0}, respectively. ` represents the number of decoding iteration. A message
vector of variable node, check node at Hmn are denoted by Q`mn and R`mn , respectively. Channel
LLR vector is also denoted by f n . As an example, the notation of the LLR vector Q`mn are
February 7, 2018

DRAFT

12

IEEE TRANSACTIONS ON COMMUNICATIONS

introduced as follows.
Q`mn =

h

Q`mn,a0, · · · , Q`mn,a

Q`mn,ai = log

iT
L 2Nbv −1

,

Pr(X = ai )
,
Pr(X = a0 )
j

π

with P(X = ai ) the probability that the random variable X takes on the values ai ∈ Z L [e 2Nbv ],

i ∈ 0, 1, · · · , L 2Nbv − 1 and Q`mn,a0 = 0, Q`mn,ai ∈ R. R`mn and f n are expression in the same
manner. The four steps of FFT-BP algorithm are described below.
Initialization: As initialization, all elements of Q0mn and R0mn , and f n are given by,
fn,ai = log

P (yn |X = ai )
,
P(yn |X = a0 )

(15)

Q0mn,ai = 0,

(16)

0
Rmn,a
= 0.
i

(17)

Variable Node Updates: the elements of variable node messages Q`mn,ai are updated via
following rule:
Q`mn,ai =

fn,ai +

Õ

R`−1
jn,ai − αmn,

j∈M\m

αmn = max Q`mn,ai .

(18)

ai

In non-systematic RASC, the variable nodes at n ≤ Ns are to be hidden nodes since information
signals are not transmitted. If the signals of a hidden node are chosen over si ∈ Z L , the message
is updated as
Q`mn,ai =



Í


 fn + j∈M\m R`−1

jn,ai − αmn

ai ∈ Z L




 −∞


otherwise.

(19)

This procedure enable the decoder to ignore impossible candidate since the input signals are
defined over Z L [ j].
DRAFT

February 7, 2018

SUBMITTED PAPER

13

Check Node Updates: the processing at both hidden node and observation node are given by
 

©
©Ö
ªª
R`mn = P −1 ­F −1 ­
F P Q`−1
(20)
®® ,
mj
«
« j∈N \n
¬¬
where P indicates permutation function which depends on the mapping space of the filter, F
represents multidimensional FFT function and, P −1 and F −1 are inverse functions corresponding
to P and F , respectively. As described in [18], there exists Fourier transform if the code are
constrained over Abelian groups. Therefore, if L is defined by power of two, RASC could be
decoded via FFT-BP since the codewords are constrained by Eisenstein rings, which are also
satisfied to the property of commutative additive groups. Note that in log-domain FFT-BP, every
LLR has to be splitted into the amplitude and the sign, but details are omitted for brevity so
that please refer to [19].
Tentative Decision: the information signal at n = 1, 2, · · · , Ns , a ∈ Z L [ j] is estimated after
`max iterations as following criterion:
sn0 = arg max fn,ai
ai

Ö

max
R`jn,a
,
i

(21)

j∈M

2) Modified EMS Algorithm: The FFT-BP algorithm can reduce the decoding complexity

to O L 2Nbv log2 L 2Nbv if and only if the number of output constellation points is a power of
two. However, the decoding complexity increases exponentially by L and Nbv . The modified
EMS algorithm proposed in [20] is introduced herein in order to alleviate this complexity issue.
In the elementary step of variable node updating, the decoder replaces the elements of the
message vector, the corresponding signal of which is not defined as Z L [ j], with the elements
of the message vector, the corresponding signal of which is defined as Z L [ j]. The decoding
complexities of both the variable node and check node updates can be reduced by each elementary
step described below.
Message Truncation:
First, we truncate the message vector for the largest Nm LLRs, denoted by Q mn [k] and Rmn [k],
k = 0, 1, · · · , Nm − 1. The values in these message vectors are sorted in decreasing order. The
February 7, 2018

DRAFT

14

IEEE TRANSACTIONS ON COMMUNICATIONS

decoding complexity can be significantly reduced when Nm  L 2Nbv because only the truncated
messages are exchanged.
Elementary Step of Variable Node Update:
For q > 3, the output of this elementary step is held as an intermediate message, and the step
is processed recursively. At the first step of the update, we compute the 2Nm messages of T as
T[k] = Rm`−1
0 n [k] + Y

(22)

T[k + Nm ] = γ Rm0 n + Rm` 00n [k],

(23)

where k = 0, 1, · · · , Nm − 1, and Y is given by




 Rm 00n [l] if βRm00 n [l] = βRm0 n [k]

Y =



if βRm00 n [l] < βRm0 n [k],
 γ Rm00 n


(24)

where γ Rm00 n is a scalar value that compensates for truncated L 2Nbv − Nm LLRs and is given by


γ Rm00 n = Rm 00n [Nm ] − log L 2Nm − Nm − η,

(25)

where η is offset value optimized by density evolution [20].
The variable node message Q mn [k] consists of Nm LLRs from T[k]. If the input signals is
defined as si ∈ Zl [ j], then the hidden node messages are updated by

where βZL [ j]





T[l]






Q mn [k] = γ0
T







 −∞

= {a0, · · · , a L 2 } represents all of

if βT[l] ∈ Zl [ j]
if βZL [ j] , βT[l], ∀l

(26)

otherwise,
the symbols defined over Z L [ j], and γT0 is given

by


γT0 = X[L 2 ] − log L 2Nm − L 2 − η.

(27)

This algorithm is slightly different from EMS for non-binary LDPC because the decoder has
a priori information of the input signals, which are constrained over Z L [ j]. Then, the decoder
DRAFT

February 7, 2018

SUBMITTED PAPER

15

replaces the LLRs even if βZL [ j] could not be calculated from Rmn0 and Rmn00 . Otherwise, if the
input signals are constrained over Eisenstein rings, then the decoder naively updates the variable
messages via (23).
Elementary Step of Check Node Update:
Figure 5 shows the elementary step of the check node update. Similar to the variable node
update, the output of this elementary step is stored as an intermediate message and recursively
updates when the row degree is greater than three.

In the check node update, we search the set S βRmn [k] , which is constrained by βQ mn0 [l] ⊕
βQ mn00 [l 0] ⊕ βRmn [k] = 0 mod Z L [e

j 2Nπ

Rmn [k] =

bv

].
max

S ( βRmn [k] )

(Q mn0 [l] + Q mn00 [l 0])

(28)

k, l, l 0 ∈ {0, 1, · · · , Nm − 1}
If we were to naively search the candidates, the complexity would be O(Nm2 ). Therefore, we
search using the virtual matrix illustrated in Fig. 5. The algorithm is as follows:
1) Introduce the values of the first column of the virtual matrix to the sorter.
2) Compute the largest value.
3) Does the symbol β associated with the largest output value exist in the output vector?
•

Yes: Remove the largest output value from the sorter.

•

No: Append the largest output value to the last element of the output vector.

4) Move the right-hand neighbor of the virtual matrix to the sorter. If there is no right-hand
neighbor, then increase the row number.
The above check node update does not stop after Nm steps because the number of element of
the output vector does not reached Nm due to existing the same symbols at Step 3 within Nm
steps. However, 2Nm steps are sufficient for a negligible degradation in decoding performance
[20].
February 7, 2018

DRAFT

16

IEEE TRANSACTIONS ON COMMUNICATIONS

Qmn′
Qmn′′

Rmn

Sorter

Nm

Fig. 5.

Elementary step of check node update of the EMS

IV. T HRESHOLD A NALYSIS AND F ILTER D ESIGN
A. Monte Carlo Density Evolution
Density evolution is a powerful tool for finding the decoding threshold, which is an important
indicator of code performance characteristics. In binary codes, the mathematical formulation of
DE is easily obtained because the BP messages are scalars [1], [2]. In the non-binary case,
tracking the true BP message distribution is impractically complex because the BP messages are
vectors. Gaussian approximation (GA) is a feasible way to track the density of BP messages for
non-binary LDPC codes because it can reduce the number of parameters to only two, namely
the mean and the variance of the density [21]. However, the message distribution of the check
node diverges increasingly from the true distribution as the degree of the check node increases.
Furthermore, GA can be used if and only if channel symmetry and permutation invariance can
be assumed [22]. Channel symmetry leads to an uncorrelated message distribution, so that the
all-zero codeword assumption may be valid. Permutation invariance means eliminating the effect
of the weight of the parity matrix, which is obtained by a random weight coefficient.
In the state-constrained signal codes, like the non-binary LDPC, the BP messages also consist of multiple parameters, and, because of the asymmetric property caused by non-uniform
DRAFT

February 7, 2018

SUBMITTED PAPER

17

modulation, the decoding performance depends on the codewords. Therefore, we introduce the
technique of adding a random coset vector, as described in [21]. The random-coset vector is
added at the end of the encoder. The random-coset elements are randomly chosen and uniformly


distributed over Z L e jπ/2Nbv . Thus, the resulting output codeword from the AWGN channel
is symmetric. The proof of this symmetric property resulting from the random-coset vector is
omitted herein. (Please refer to [21] for the proof.) Although the channel symmetry can be
assumed, permutation invariance cannot be assumed because the weight coefficients are defined
by the IIR filter coefficient. MC-DE has been introduced as alternative approach for tracking the
density with multiple parameters [16], [23], [24]. One advantage of MC-DE is that the estimated
threshold is more accurate than the Gaussian approximation method because the analysis is nonparametric [16]. Thanks to the random-coset settings for the RASC, as described above, we can
straightforwardly introduce MC-DE to approximate the noise threshold σth as Algorithm 1.
In this paper, we set several parameters for MC-DE as follows: number of threshold calculations, Rmax = 10; number of message samples, Nsam = 5000; maximum number of iterations,
`max = 100; decoding error threshold, Pth = 10−4 , which means that decoding could be regarded
as successful when all symbols are correctly decoded; and threshold precision, σ = 10−5 . In
the subsequent section, we present the results of the optimum parameters and the corresponding
noise threshold.

B. Searching for the Best Filter
As described in the Introduction, an efficient search algorithm for the filter coefficient of stateconstrained signal codes has not been reported [14]. We therefore introduce an efficient search
method via the proposed MC-DE as Algorithm 2.
The best four filters with several parameters are shown in Tables I and II. Several filters appear
to have the same or similar thresholds. For instance, in Table I, FB = 7 and FB = 11 have the
same threshold (1.14 dB). Similarly, FB = 13 and FB = 14 have the same threshold (3.10 dB).
February 7, 2018

DRAFT

18

IEEE TRANSACTIONS ON COMMUNICATIONS

Algorithm 1 Threshold calculation via Monte-Carlo density evolution for RASC
function σth = MCDE(FB)
σavr = 0
for i = 1 to Rmax do
repeat
σ=

σH +σL
2

Initialization:
Q nI = [0, · · · , 0], n = {1, 2, · · · , Nsam }
Q nP = [0, · · · , 0], n = {1, 2, · · · , Nsam }
RnI = [0, · · · , 0], n = {1, 2, · · · , Nsam }
RnP = [0, · · · , 0], n = {1, 2, · · · , Nsam }
Q ∗ = [Q∗1, · · · , Q∗Nsam ]
R ∗ = [R1∗, · · · , RN∗ sam ]
for ` = 0 to `max do
VN processing for parity nodes:
for n = 1 to Nsam do
Randomly Choose from R P
Sample the channel LLR f
Compute Q nP according to (18)
end for
CN processing for information nodes:
for n = 1 to Nsam do
Randomly choose from Q I and Q P
Compute R I according to (20)
end for

DRAFT

February 7, 2018

SUBMITTED PAPER

19

VN processing for information nodes:
for n = 1 to Nsam do
Randomly choose from R I
Compute Q nI according to (19)
end for
CN processing for parity nodes:
for n = 1 to Nsam do
Randomly choose from Q I and Q P
Compute RnP according to (20)
end for
end for
if Decoding error rate is Pe ≤ Pth then
σL = σ
else
σH = σ
end if
until (σH − σL ) < σ
σavr = σavr + σL
end for
return σth = σavr /Rmax
end function

February 7, 2018

DRAFT

20

IEEE TRANSACTIONS ON COMMUNICATIONS

Algorithm 2 Calculate the thresholds for filter coefficients
for i = 0 to L 2Nbv do
if FB = i is a bijective filter then
Calculate σi = MCDE(i)
else
σi = NULL
end if
end for
Sorting σi without NULL
TABLE I
B EST FOUR FILTERS FOR L = 2, Nbv = 2, AND q = 2.

feedback index

taps

threshold[dB]

7

(1,1),(1,0)

1.14

11

(1,1),(0,1)

1.14

13

(1,0),(1,1)

3.10

14

(0,1),(1,1)

3.10

These filters are converted by affine transformation with each other, e.g., by rotation by 90
degrees, extension, and reduction. This property can be exploited in order to further truncate the
candidate filters.

C. Thresholds for Different Numbers of Basis
Figure 6 shows the difference between the noise threshold of the RASC and the Shannon
capacity. In this figure, the impact of the number of basis Nbv on the threshold is analyzed. The
indices of the best filters for each Nbv are shown in this figure because different values of Nbv
DRAFT

February 7, 2018

SUBMITTED PAPER

21

TABLE II
B EST FOUR FILTERS FOR L = 3, Nbv = 2, AND q = 2.

feedback index

taps

threshold[dB]

45

(0,0),(2,1)

3.85

63

(0,0),(1,2)

3.85

36

(0,0),(1,1)

3.86

72

(0,0),(2,2)

3.86

have different optimum filters. Note that some affine transformed filters have the same threshold,
as described above. Thus, the filters must be searched for every target Nbv . Furthermore, the
number of repetitions q must be optimized for each Nbv . Based on our results, the optimal value
of q is three for Nbv = 2, whereas that for Nbv ≥ 3 is two. In non-binary LDPC, the optimum
column weight is two for a large alphabet size, e.g., greater than or equal to GF(64) [25].
Unfortunately, the threshold does not improve monotonically as Nbv increases. We believe that
the reason for which is the dense constellation of output signals. As shown in Figs. 3-(a), 3-(b),
and 3-(c), the distance between the signal points decreases as Nbv increases. Thus, increasing
N[ bv] improves coding gain but results in a short Euclidean distance of the constellation.

D. Thresholds for Different Numbers of Repetitions
The effect of the number of repetition q is shown in Fig. 7. Similar to the previous results, the
optimum filter varies depending on q. The difference between the noise threshold of the RASC
and the Shannon limit for Nbv = 3 and FB = 44 is the smallest among all other parameters
at q = 2 (= 0.79 dB). However, for q ≥ 3, the thresholds for Nbv = 3 are inferior to those for
Nbv = 2. This conclusion can also be found in the literature on non-binary LDPC code, where
for a column weight greater than three, the performance of the codes over higher-order fields is
February 7, 2018

DRAFT

22

IEEE TRANSACTIONS ON COMMUNICATIONS

Fig. 6.

Thresholds for different numbers of basis for L = 2.

worse than that of the codes over lower-order fields [25].

E. Thresholds for Different Input Constellation Sizes

The impact of the input constellation size L is shown in Fig. 8. Since the computational
complexity required for L ≥ 3 with Nbv ≥ 3 is enormous, only the case of Nbv = 2 is illustrated.
In contrast to the impact of Nbv , the difference between the noise threshold of the RASC and the
Shannon capacity decreases as L increases. The reason for this behavior, which differs from that
for increasing Nbv , is that the distances between the output signals are greater than for fixed L
because the signal constellation space is expanded by L. Based on this result, the RASC appears
to have the excellent property whereby increasing the transmission rate improves the threshold.
DRAFT

February 7, 2018

SUBMITTED PAPER

Fig. 7.

23

Thresholds for different numbers of repetitions for L = 2 with Nbv = 2 and Nbv = 3.

F. Threshold for Different Input Constraints
Finally, the effect of the input signal constraint is shown in Fig. 9. In this case, the optimum
filters for the same q and Nbv differ depending on the constraint. Interestingly, FB = 1, which
is an identity mapping function, is the best filter for q = 3 and L = Nbv = 2. We believe that the
reason for this is that when the input signals are chosen over Z L [e
state due to the summation of signals is chosen over Z L [e

j 2Nπ

bv

j 2Nπ

bv

], the transition of the

]. Then, the codeword distances

increase, even if the signals are mapped into the same mapping space by FB = 1.
V. N UMERICAL R ESULTS
In this section, the finite length performances of the RASC are shown. We assume that the
information signal length is Ns = 103 , that the interleaver of the encoder is a random interleaver,
that the number of iterations of the SP algorithm is 100, and that the filters are chosen as
described in the previous section.
February 7, 2018

DRAFT

24

IEEE TRANSACTIONS ON COMMUNICATIONS

Fig. 8.

Thresholds for different input constellation sizes.

A. Performance of the RASC with FFT-BP
Figure 10 shows the SER of finite-codeword-length RASC with FFT-BP decoding. The input
signals are 4-QAM (L = 2), and the filters are chosen as FB = 11 and FB = 44 for Nbv = 2 and
Nbv = 3, respectively. As shown in the figure, the relationship between Nbv and q is the same
as that determined by a previous threshold analysis. Namely, for Nbv = 2, the performance for
q = 3 is superior to that for q = 2 in both the waterfall and error floor regions. In contrast, for
Nbv ≥ 3, the threshold of q = 3 is inferior to that of q = 2. Interestingly, the performance for
the error floor region depends on the filter but not the number of states. Therefore, the best filter
can only be chosen if we find the best threshold via MC-DE, because the overall performance
is defined by the filter.
Next, we compare the performance of the RASC with that of the turbo signal codes for the
same codeword length Ns = 1000 and input constellation L = 2. Due to a termination, the
DRAFT

February 7, 2018

SUBMITTED PAPER

Fig. 9.

25

Thresholds for different input constraints for L = 2 and Nbv = 2

1000
= 0.9995 bits
transmission rates of the RASC and the turbo signal codes are RRASC = 2 × 2000+1
1000
per channel use (bits/c.u.) and Rtur bo = 2 × 2000+8
= 0.9960 bits/c.u., respectively. For the turbo

signal codes, we assume that the indices of the feedback and feedforward filters are FB=11 and
FB=81, respectively. This optimum filter setting was reported in [14]. The decoding algorithm is
the BCJR algorithm, and the number of iterations is 25. As shown in Fig. 10, the performance
of the RASC with Nbv = 2 is close to that of turbo signal codes (within 0.2 dB, which is a
negligible performance loss) in the waterfall region. Furthermore, in the error floor region, the
error probability of the RASC is approximately 1/3 better than that of the turbo signal codes.
These results indicate that the RASC can provide superior performance to turbo signal codes
with only a one-tap feedback filter.
February 7, 2018

DRAFT

26

IEEE TRANSACTIONS ON COMMUNICATIONS

Turbo SC

10-1

SER

10-2

10-3

10-4

Fig. 10.

S.L. for 1 [bit/cu]
S.L. for 2/3 [bits/cu]

-2

-1

0
SNR[dB]

1

2

3

Performances of the optimized filter for L = 2 and Nbv = 2, 3. The filter index is FB = 11 for Nbv = 2 and FB = 44

for Nbv = 3.

B. Performance of the RASC with EMS
Figure 11 shows the SER performance for the given L and Nbv = 2 obtained using the proposed
modified EMS decoder. In this figure, full BP indicates the naive sum-product algorithm whereby
all sets of the signals that satisfy the check equation are searched and calculated for the message
updates in check nodes so that the decoder does not use FFT-BP algorithm since FFT algorithm
over Eisenstein rings with L > 2 cannot be represented by multidimensional FFT form as that
with L = 2. The number of output constellation points L 2Nbv for L = 3 and L = 4 are 81
and 256, respectively. The decoding complexities of BCJR, FFT-BP, and EMS are O(L 4Nbv ),
O(L 2Nbv log2 L 2Nbv ), and O(Nm log2 Nm ), respectively. Therefore, the decoding complexity of
EMS can be reduced if Nm is chosen so as to be much smaller than L 2Nbv . For example, when
Nm = L 2Nbv /2, the decoding complexity of EMS becomes a quarter of that of the BCJR, and
DRAFT

February 7, 2018

SUBMITTED PAPER

27

SER

10-1

10-2

10-3

10-4
3.5

Fig. 11.

4.0

4.5

5.0

5.5

6.0

SNR [dB]

6.5

7.0

7.5

8.0

8.5

Performance with the EMS decoder for different values of L and Nm . For all curves, Nbv =2. The filter index is

FB = 45 for L = 3 and FB = 224 for L = 4. η = {−3.0, −3.5, −4.7, −5.5} for Nm = {20, 40, 64, 128}, respectively.

when Nm = L 2Nbv /4, the decoding complexity of the EMS becomes one-sixteenth that of the
BCJR and a quarter of that of FFT-BP. Therefore, in this section, Nm = 40 and Nm = 20 are set
for L = 3 and, Nm = 128 and Nm = 64 are set for L = 4.
Figure 11 indicates that the performance loss is only approximately 0.5 dB when Nm = L 2Nbv /2
and is only approximately 1.0 dB when Nm = L 2Nbv /4. Furthermore, our algorithm does not
degrade the error floor performance because the curves with the EMS decoder decrease until
reaching the error floor of full BP. As a result, the EMS decoder can dramatically reduce the
decoding complexity without a significant performance loss.

VI. C ONCLUSION
In this paper, we proposed a new state-constrained signal code based on RA codes. The
proposed code has several advantages, including a simpler encoder and decoder, as compared
February 7, 2018

DRAFT

28

IEEE TRANSACTIONS ON COMMUNICATIONS

to turbo signal codes, with approximately the same performance in the waterfall region and
a slightly better performance in the error floor region. Furthermore, we have found a design
criterion of the filter coefficient via MC-DE. We summarize the properties of the threshold in
terms of the following three parameters:
1) The number of basis Nbv can make improve the threshold, but an excessive value of Nbv
leads to threshold degradation.
2) An optimum repetition number q exists for a given Nbv . In particular, for a large number
of states, L 2Nbv ≥ 64, q = 2 is optimum in terms of the threshold.
3) The number of states L can improve both the transmission rate and the threshold.
Simulation results have shown that the optimum filters for given values of Nbv , q, and L perform
well in the waterfall and error floor regions with short codeword lengths. Overall performance
optimization for the regular RASC can be performed by MC-DE. Furthermore, we proposed
a modified EMS decoder. Simulation results indicate that the modified EMS decoder does not
cause a significant performance loss of more than 1 dB as compared to the performance of the
full BP decoder, while the decoding complexity is reduced to less than 25% of that of BCJR
and FFT-BP decoder. Finally, the proposed code can be easily generalized to irregular and other
turbo-like codes, such as accumulate-repeat-accumulate codes and braided convolutional codes,
to more closely approach the Shannon limit.

ACKNOWLEDGMENT

The authors are grateful to Hideki Ochiai and Tadashi Wadayama for their help in discussion
and sharing their insights. The authors also thank to Brian M. Kurkoski for basic education
in lattice coding theory. This work was supported in part by JSPS Grant-in-Aid for Scientific
Research(A) Grant number 16H02345.
DRAFT

February 7, 2018

SUBMITTED PAPER

29

A PPENDIX A
N ECESSARY CONDITION TO SATISFY THE PARITY CHECK EQUATION IN TURBO SIGNAL
CODES

For simplify, we next consider the minimum encoder of turbo signal codes, which is given by
xt = f1 ut−1 + f0 (st + g1 ut−1 + bt ) .

(29)

From this equation, there are three filter coefficients, f0 , f1 , and g1 . In this setting, the parity
check matrix of (29) is given by



















1 0 0 · · · 0 0 0 

.
1 1 0 . . 0 0 0 


..
. 0 0 0 ,
0 1 1


..
. 1 1 0 
0 0 0


..
. 0 1 1 
0 0 0


1 0 0 ··· 0 0 0
.
1 1 0 .. 0 0 0
.
0 1 1 .. 0 0 0
.
0 0 0 .. 1 1 0
.
0 0 0 .. 0 1 1

(30)

where the left-hand side of this matrix corresponds to information signals, and the right-hand
side corresponds to parity signals. Based on this matrix, the parity check equation at t = 1 is
given by
s0 + s1 + x0 + x1 = 0

h
i
mod Z L e jπ/2Nbv .

(31)

From (29), the reformulation of (31) is given by
h
i
mod Z L e jπ/2Nbv .

(1 + f0 + f0 g1 + f1 )s0 + (1 + f0 ) s1 = 0

(32)

Therefore, the necessary conditions for f0 , f1 , and g1 are given by
f0 = −1 + j0
f1 = g1 .
February 7, 2018

h

mod Z L e

jπ/2Nbv

i
(33)
DRAFT

30

IEEE TRANSACTIONS ON COMMUNICATIONS

For L = 2, the coded signal at t is given by
xt =

f1 ut−1 + (st + f1 ut−1 + bt )

= st .

(34)

Thus, the mapping space of the filters of turbo signal codes is defined as an identity mapping
in order to satisfy the parity check equation.

R EFERENCES
[1] T. J. Richardson and R. L. Urbanke, “The Capacity of Low-Density Parity-Check Codes under Message-Passing Decoding,”
IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 599–618, 2001.
[2] S.-Y. Chung, G. D. Forney, T. J. Richardson, and R. Urbanke, “On the Design of Low-Density parity-check codes within
0.0045 dB of the Shannon limit,” IEEE Commun. Lett., vol. 5, no. 2, pp. 58–60, 2001.
[3] S. ten Brink, “Convergence Behavior of Iteratively Decoded Parallel Concatenated Codes,” IEEE Trans. Commun., vol. 49,
no. 10, pp. 1727–1737, 2001.
[4] T. J. Richardson, M. A. Shokrollahi, and R. L. Urbanke, “Design of Capacity-Approaching Irregular Low-Density ParityCheck Codes,” IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 619–637, 2001.
[5] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding: Turbo-codes.
1,” in Proc. of IEEE ICC 1993, vol. 2, 1993, pp. 1064–1070 vol.2.
[6] G. Ungerboeck, “Channel coding with multilevel/phase signals,” IEEE Trans. Inf. Theory, vol. 28, no. 1, pp. 55–67, 1982.
[7] G. Caire, G. Taricco, and E. Biglieri, “Bit-Interleaved Coded Modulation,” IEEE Trans. Inf. Theory, vol. 44, no. 3, pp.
927–946, 1998.
[8] U. Erez and R. Zamir, “Achieving 1/2 log (1+SNR) on the AWGN Channel with Lattice Encoding and Decoding,” IEEE
Trans. Inf. Theory, vol. 50, no. 10, pp. 2293–2314, 2004.
[9] J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups. Springer Science & Business Media, 2013, vol.
290.
[10] M. R. Sadeghi, A. H. Banihashemi, and D. Panario, “Low-density parity-check lattices: Construction and decoding analysis,”
IEEE Trans. Inf. Theory, vol. 52, no. 10, pp. 4481–4495, 2006.
[11] A. Sakzad, M. Sadeghi, and D. Panario, “Turbo lattices: Construction and performance analysis,” CoRR, vol.
abs/1108.1873, 2011. [Online]. Available: http://arxiv.org/abs/1108.1873
[12] O. Shalvi, N. Sommer, and M. Feder, “Signal codes: Convolutional lattice codes,” IEEE Trans. Inf. Theory, vol. 57, no. 8,
pp. 5203–5226, Aug 2011.
[13] F. R. Kschischang, B. J. Frey, and H. A. Loeliger, “Factor Graphs and the Sum-Product Algorithm,” IEEE Trans. Inf.
Theory, vol. 47, no. 2, pp. 498–519, 2001.
[14] P. Mitran and H. Ochiai, “Parallel concatenated convolutional lattice codes with constrained states,” IEEE Trans. Commun.,
vol. 63, no. 4, pp. 1081–1090, 2015.
[15] D. Divsalar, D. Jin, and R. McEliece, “Coding theorems for turbo-like codes,” in Allerton Conference, 1998, pp. 201–210.
[16] M. Gorgolione, “Analysis and Design of Non-Binary LDPC Codes over Fading Channels,” Ph.D. dissertation, CergyPontoise Univ., 2012.
[17] D. Declercq and M. Fossorier, “Decoding Algorithms for Nonbinary LDPC Codes Over GF(q),” IEEE Trans. Commun.,
vol. 55, no. 4, pp. 633–643, 2007.
[18] A. Goupil, M. Colas, G. Gelle, and D. Declercq, “FFT-Based BP Decoding of General LDPC Codes Over Abelian Groups,”
IEEE Trans. Commun., vol. 55, no. 4, pp. 644–649, 2007.
[19] G. J. Byers and F. Takawira, “Fourier Transform Decoding of Non-Binary LDPC Codes,” in in Proc. of SATNAC. Spier
Wine Estate, Western Cape, South Africa, 2004.
DRAFT

February 7, 2018

SUBMITTED PAPER

31

[20] A. Voicila, D. Declercq, F. Verdier, M. Fossorier, and P. Urard, “Low-Complexity Decoding for Non-Binary LDPC Codes
in High Order Fields,” IEEE Trans. Commun., vol. 58, no. 5, pp. 1365–1375, 2010.
[21] A. Bennatan and D. Burshtein, “Design and Analysis of Nonbinary LDPC Codes for Arbitrary Discrete-Memoryless
Channels,” IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 549–583, 2006.
[22] G. Li, I. J. Fair, and W. A. Krzymien, “Density Evolution for Nonbinary LDPC Codes Under Gaussian Approximation,”
IEEE Trans. Inf. Theory, vol. 55, no. 3, pp. 997–1015, 2009.
[23] B. M. Kurkoski, K. Yamaguchi, and K. Kobayashi, “Single-Gaussian Messages and Noise Thresholds for Decoding LowDensity Lattice Codes,” in Proc. of IEEE ISIT 2009, 2009, pp. 734–738.
[24] H. Uchikawa, B. M. Kurkoski, K. Kasai, and K. Sakaniwa, “Threshold Improvement of Low-Density Lattice Codes via
Spatial Coupling,” in Proc. of ICNC 2012, 2012, pp. 1036–1040.
[25] M. C. Davey, “Error-Correction using Low-Density Parity-Check Codes,” Ph.D. dissertation, University of Cambridge,
2000.

February 7, 2018

DRAFT

