entropy
Article
Skew Convolutional Codes
Vladimir Sidorenko 1,* , Wenhui Li 2, Onur Günlü 3and Gerhard Kramer 1
1Institute for Communications Engineering, Technical University of Munich, 80333 München, Germany;
gerhar[email protected]
2Skolkovo Institute of Science and Technology, 143026 Moscow, Russia; w[email protected]
3Information Theory and Applications Chair, Technical University of Berlin, 10623 Berlin, Germany;
*Correspondence: vladimir[email protected]
Received: 30 October 2020; Accepted: 30 November 2020; Published: 2 December 2020
Abstract:
A new class of convolutional codes, called skew convolutional codes, that extends the class
of classical fixed convolutional codes, is proposed. Skew convolutional codes can be represented as
periodic time-varying convolutional codes but have a description as compact as fixed convolutional
codes. Designs of generator and parity check matrices, encoders, and code trellises for skew
convolutional codes and their duals are shown. For memoryless channels, one can apply Viterbi or
BCJR decoding algorithms, or a dualized BCJR algorithm, to decode skew convolutional codes.
Keywords: convolutional codes; skew polynomials; time-varying codes; dual codes; trellises
1. Introduction
Convolutional codes were introduced by Elias in 1955 [
1
]. With the discovery that convolutional
codes can be decoded with Fano sequential decoding [
2
], Massey threshold decoding [
3
], and, above all,
Viterbi decoding [
4
], they became quite widespread in practice. Convolutional codes are still widely
used in telecommunications, e.g., in Turbo codes [
5
] and in the WiFi IEEE 802.11 standard [
6
],
in cryptography [7], etc.
The most common are binary convolutional codes; however, communication with higher orders
of modulation [
8
] or streaming of data [
9
] require non-binary convolutional codes. It is known that periodic
time-varying convolutional codes improve the free distance and weight distribution over fixed convolutional
codes; see, e.g., Mooser [
10
] and Lee [
11
]. This is the motivation to introduce a new class of periodic
time-varying non-binary convolutional codes, i.e., skew convolutional codes. These codes are based on
the non-commutative ring of skew polynomials over finite fields and on the skew field of their fractions.
Block codes based on skew polynomials were studied by various authors; see, e.g., publications
of Gabidulin [
12
], Boucher and Ulmer [
13
,
14
], Martínez-Peñas [
15
], Gluesing-Luerssen [
16
], Abualrub,
Ghrayeb, Aydin, and Siap [17].
Convolutional codes are nonblock linear codes over a finite field, but it can be advantageous
to treat them as block codes over certain infinite fields. We will use both approaches. Classical
convolutional codes are described by usual polynomials. The product of the polynomials corresponds
to convolution of vectors of their coefficients and this gives fixed-in-time classical convolutional codes.
We replace usual polynomials by skew polynomials to define the new codes. The product of skew
polynomials corresponds to skew convolution of their coefficients, which can be obtained by varying
elements in the usual convolution. In this way, we obtain time varying convolutional codes.
Our goal is to define and to give a first encounter with skew convolutional codes. In Section 2,
we define skew convolutional codes. In Section 3, we obtain generator matrices and encoders for skew
codes and show that skew codes are equivalent to time-varying convolutional codes. Some useful
Entropy 2020,22, 1364; doi:10.3390/e22121364 www.mdpi.com/journal/entropy
Entropy 2020,22, 1364 2 of 17
properties of skew codes are considered in Section 4. Section 5introduces dual skew convolutional
codes. Trellis decoding of skew codes is considered in Section 6. Section 7concludes the paper.
2. Skew Convolutional Codes
2.1. Skew Polynomials and Fractions
Consider a field
F
and an automorphism
θ
of the field. Later on, we will use the finite field
F=Fqm, where qis a prime power, with the Frobenius automorphism
θ(a) = aq,∀a∈F. (1)
The composition of automorphisms is denoted as
θ(θ(a)) = θ2(a)
, and, for any integer
i
,
we have
θi(a) = θ(θi−1(a))
. The identity automorphism
θ(a) = a
is denoted as
θ=id
. For the
automorphism (1) for all a∈F, we have θi(a) = aqiand θm=id since aqm=a.
Denote by
R=F[D
;
θ]
the non- commutative ring [
18
] of skew polynomials in the variable
D
over
F(with zero derivation) such that
R=F[D;θ] = {a(D) = a0+a1D+· · · +anDn|ai∈Fand n∈N}.
The skew polynomials look like usual polynomials
F[D]
where the coefficients
ai
are placed to the
right of the variable
D
. The addition in
R
is as for usual polynomials from
F[D]
. The multiplication is
defined by the basic rule
Da =θ(a)D(2)
and is extended to all elements of
R
by associativity and distributivity; see Example 1below. The ring
R
has a unique left skew field of fractions
Q
, from which it inherits its linear algebra properties, see,
e.g., [19] for more details.
Example 1.
To demonstrate our results, we use the field
FQ=Fqm=F22
,
q=
2,
m=
2, with automorphism
θ(a) = aq=a2
for all
a∈F22
. The field
F22
consists of the elements
{
0, 1,
α
,
α2}
, where a primitive element
α
satisfies α2+α+1=0and the following relations hold:
α2=α+1,
α3=1,
α4=α,
and ∀i∈Zθi=(θif i is odd,
id if i is even.
Let a(D) = 1+αD and b(D) = α2+D, a(D),b(D)∈ R. Using (2), we compute the product ab as
a(D)b(D) = (1+αD)(α2+D) = (α2+D) + αθ(α2)D+αD2=α2+αD+αD2
while the product ba is
b(D)a(D) = (α2+D)(1+αD) = (α2+D) + α3D+θ(α)D2=α2+α2D2.
In this example, we see that a(D)b(D)6=b(D)a(D).
The left skew field
Q
consists of fractions
b(D)
a(D)=a−1(D)b(D)∈ Q
for all
a(D)
,
b(D)∈ R
,
a(D)6=
0.
Every fraction can be expanded as the left skew Laurent series in increasing powers of
D
. In our example,
the inverse element 1
a(D)=a(D)−1is expanded using long devision as follows:
a−1(D) = 1+αD+D2+αD3+D4+. . .
Entropy 2020,22, 1364 3 of 17
with
a−1(D)a(D) = a(D)a−1(D) =
1. We can expand the left fraction
b(D)
a(D)=a−1(D)b(D)
by long left
division or equivalently by left multiplication b(D)by a−1(D)and get
b(D)
a(D)=a−1(D)b(D) = α2+αD+D2+αD3+D4+. . . .
Notice that the right fraction b(D)a−1(D) = α2, since b(D) = α2+D=α2(1+αD) = α2a(D).
2.2. Definition of Skew Convolutional Codes
Much of linear algebra can be generalized from vector spaces over a field to (either left or right)
modules over the skew field
Q
. Indeed, it is shown in [
19
] that any left
Q
-module
C
is free, i.e., it has a
basis, and any two bases of Chave the same cardinality, the dimension of C.
Definition 1
(Skew convolutional code)
.
Given an automorphism
θ
of the field
F
, a skew convolutional
[n
,
k]
code Cover the field Fis a left sub-module of dimension k of the free module Qn.
The elements of the code
C
are called its codewords. A codeword
v(D) = v(1)(D), . . . , v(n)(D)
is an
n
-tuple over
Q
, where every component
v(i)(D)
is a fraction of skew polynomials from
R
.
The code
C
is
F=Fqm
-linear. Let the weight of every codeword be defined by some selected metric.
The free distance
df
of a skew convolutional code is defined to be the minimum nonzero weight of
any codeword.
For the Hamming metric, which is the most interesting for applications, the weight of a fraction
v(i)(D)
is the number of nonzero coefficients in its expansion as a left skew Laurent series from
F((D))
in increasing powers of
D
. The weight of a codeword is the sum of weights of its components.
Another interesting metric is sum-rank metric, which will be defined later.
2.3. Relations to Fixed Convolutional Codes
Lemma 1.
The class of skew convolutional codes includes the class of fixed (time-invariant) convolutional codes.
Proof.
A time-invariant convolutional
[n
,
k]
code
e
C
over the field
F
is defined as a
k
-dimensional
subspace of
F(D)n
. Take the identity automorphism
θ=id
. Then, the ring
R=F[D
;
θ]
becomes a ring
F[D]
of usual commutative polynomials. The skew field of fractions
Q
becomes the field of rational
functions
F(D)
. In this case, by Definition 1, the skew convolutional code
C
coincides with the classical
fixed code e
C.
3. Encoding Skew Convolutional Codes
3.1. Polynomial Form of Encoding
Agenerator matrix of a skew convolutional
[n
,
k]
code
C
is a
k×n
matrix
G(D)
over the skew field
Q
whose rows form a basis for the code
C
. If the matrix
G(D)
is over the ring
R
of skew polynomials,
then
G(D)
is called a polynomial generator matrix for
C
. Every skew code
C
has a polynomial generator
matrix. Indeed, given a generator matrix
G(D)
over the skew field of fractions
Q
, a polynomial
generator matrix can be obtained by left multiplying each row of
G(D)
by the least common left
multiple of the denominators in that row. In the paper, we focus on polynomial generator matrices
and corresponding encoders.
By Definition 1, every codeword
v(D)
of a skew code
C
, which is an
n
-tuple over the skew field
of fractions Q
v(D) = v(1)(D),v(2)(D), . . . , v(n)(D),v(j)(D)∈ Q, 1 ≤j≤n(3)
Entropy 2020,22, 1364 4 of 17
can be written as
v(D) = u(D)G(D)(4)
where u(D)is a k-tuple (k-word) over Q:
u(D) = u(1)(D),u(2)(D). . . , u(k)(D),u(i)(D)∈ Q, 1 ≤i≤k(5)
and is called an information word,
G(D)
is a generator matrix of
C
,
G(D)∈ Qk×n
or
G(D)∈ Rk×n
.
Relation (4) already provides an encoder. This encoder (4) is just an encoder of a block code over
Q
and
the skew code
C
can be considered as the set of
n
-tuples
v(D)
over
Q
that satisfy (4), i.e.,
C={v(D)}
.
However, to use the code in practice we need to write components of
u(D)
and
v(D)
as skew
Laurent series, i.e., we have
u(i)(D) = u(i)
0+u(i)
1D+u(i)
2D2+. . . , i=1, . . . , k(6)
and
v(j)(D) = v(j)
0+v(j)
1D+u(j)
2D2+. . . , j=1, . . . , n. (7)
Actually, in a Laurent series, the lower (time) index of coefficients can be a negative integer,
but, in practice, the information sequence
u(i)(D)
should be causal for every component
i
, that is,
the coefficients
u(i)
t
are zeros for time
t<
0. Causal information sequences should be encoded into
causal code sequences; otherwise, an encoder can not be implemented, since it should output code
symbols before it receives an information symbol.
Denote the block of information symbols that enters an encoder at time t=0, 1, . . . by
ut=u(1)
t,u(2)
t, . . . u(k)
t∈Fk. (8)
The block of code symbols that leaves the encoder at time t=0, 1, . . . is denoted by
vt=v(1)
t,v(2)
t, . . . v(n)
t∈Fn. (9)
Combining (5), (6), and (8), we obtain the following information series with vector coefficients:
u(D) = u0+u1D+... +utDt+. . . , u(D)∈F((D))k. (10)
Using (3), (7), and (9), we write a codeword as a series
v(D) = v0+v1D+... +vtDt+. . . , v(D)∈F((D))n. (11)
One can write a skew polynomial generator matrix
G(D) = gij(D)∈ Rk×n
as a skew
polynomial with matrix coefficients:
G(D) = G0+G1D+G2D2+... +GµDµ(12)
where
µ
is the maximum degree of polynomials
gij(D)
. The matrices
Gi
are
k×n
matrices over the
field Fand µis called the generator matrix memory.
From (4), (10), and (11), we obtain that
vt
is a coefficient in the product of skew series
u(D)
and
skew polynomial G(D), which is the following skew convolution (see Figure 1)
vt=utθt(G0) + ut−1θt−1(G1) + · · · +ut−µθt−µ(Gµ)(13)
where ut=0 for t<0. This encoding rule explains the title skew convolutional code, which can be also
seen as the set C={v(D)}of series v(D)defined in (11).
Entropy 2020,22, 1364 5 of 17
θt−µ(Gµ)θt−2(G2)θt−1(G1)θt(G0)
ut−µut−2ut−1
+ + +
ut,ut+1, . . .
v0, . . . , vt
. . .
. . .
Figure 1. Encoder of a skew convolutional code.
At time
t
, the decoder observes an information block
ut
of
k
symbols from
F
and outputs the code
block
vt
of
n
code symbols from
F
using (13); hence, the code rate is
R=k/n
. The encoder (13) uses
ut
and also
µ
previous information blocks
ut−1
,
ut−2
,
. . .
,
ut−µ
, which should be stored in the encoder’s
memory; this is why µis also the encoder memory.
The coefficients
θt−i(Gi)
,
i=
0, 1,
. . .
,
µ
in the encoder (13) depend on the time
t
. Hence, the skew
convolutional code is a time-varying classical convolutional code. Denote
τ=min ni>0 : θi(Gj) = Gj∀j=0, 1, . . . , µo. (14)
For the field
F=Fqm
, we have
θm=θ0
; hence, the coefficients in (13) are periodic with period
τ≤m
, and the skew convolutional code is periodic with period
τ≤m
. The period
τ
can be less than
m
if
all the matrices G0, . . . Gµare over a subfield of Fqm.
3.2. Scalar Form of Encoding
The input of the encoder can also be written as an information sequence of k-blocks over F
u=u0,u1,u2, . . . , ut, . . . (15)
and the output as a code sequence of n-blocks over F
v=v0,v1,v2, . . . , vt, . . . . (16)
Then, the encoding rule (13) can be written in a scalar form
v=uG (17)
with semi-infinite scalar generator block matrix
G=
G0G1G2. . . Gµ
θ(G0)θ(G1). . . θ(Gµ−1)θ(Gµ)
θ2(G0). . . θ2(Gµ−2)θ2(Gµ−1)θ2(Gµ)
. . .
. (18)
Thus, a skew convolutional code can be equivalently represented in a scalar form as the set
C={v}of sequences vdefined in (16) that satisfy (17).
Entropy 2020,22, 1364 6 of 17
3.3. Relations between Skew and Classical Convolutional Codes
In case of identity automorphism,
θ(a) = a
, the scalar generator matrix of the skew code becomes
G0=
G0G1G2. . . Gµ
G0G1. . . Gµ−1Gµ
G0. . . Gµ−2Gµ−1Gµ
. . .
, (19)
which is a generator matrix of a fixed convolutional code [
20
]. For fixed convolutional codes,
polynomial generator matrices with
G0
of full rank
k
are of particular interest [
20
] (Chapter 3). The skew
convolutional codes use the following nice property: if
G0
has full rank, then
θi(G0)
has full rank as
well for all i.
Time-varying classical convolutional codes are defined by the following generator matrices in [
20
],
Gvar =
G0,0 G1,1 Gµ,µ
G1,0
.
.
.Gµ,µ−1Gµ+1,µ
.
.
.Gµ+1,µ−1
.
.
.
Gµ,0
.
.
.
Gµ+1,0
(20)
where the first index
t
in
Gt,i
is time index. The code defined by the generator matrix
Gvar
in
(20)
is
called τ-periodic if the columns (GT
t,µ, . . . , GT
t,0)T,t≥µ, repeat with period τ.
Lemma 2. A scalar generator matrix (18) of a skew code can be written in the following equivalent form:
G=
e
G0θ(e
G1)θµ(e
Gµ)
θ(e
G0).
.
.θµ(e
Gµ−1)θµ+1(e
Gµ)
.
.
.θµ+1(e
Gµ−1).
.
.
θµ(e
G0).
.
.
θµ+1(e
G0)
. (21)
Proof. The statement follows from the change of variables Gi=θi(e
Gi)for i=1, 2, . . . , µ.
From
(14)
,
(20)
and
(21)
, we see again that a skew code defined by a generator matrix (21) is a
τ-periodic classical convolutional code. Thus, above we proved the following theorem.
Theorem 1.
Given a field
F=Fqm
with automorphism
θ
in (1), any skew convolutional
[n
,
k]
code
C
over
F
is equivalent to a periodic time-varying (classical) convolutional
[n
,
k]
code over
F
, with period
τ≤m
(14).
If
G(D)
is a skew polynomial generator matrix (12) of the code
C
, then the scalar generator matrix
G
of the
time-varying code is given by (18) or (21).
Not every periodic classical convolutional code can be represented as a skew code. Indeed,
e.g., the submatrix
G1,0
in
(20)
can be selected independently of
G0,0
while corresponding submatrix
θ(e
G0)
in
(21)
is completely determined by
e
G0
. Hence, a class of skew convolutional codes is a subclass
of periodic classical convolutional codes.
Given the field
Fqm
, the automorphism
θ
in
(1)
, and the code memory
µ
, an
[n
,
k]
skew
convolutional code is defined by a generator matrix
G
in
(21)
. To specify the matrix, we should
fix elements of
µ+
1 matrices
e
G0
,
. . .
,
e
Gµ
of size
k×n
. Hence, we should define
(µ+
1
)kn
field
Entropy 2020,22, 1364 7 of 17
elements. Since a classical convolutional code corresponds to the identity automorphism
θ=id
,
the description of skew and classical codes require the same number of field elements.
The number of skew
[n
,
k]
convolutional codes over
FQ=Fqm
of memory
µ
with fixed
automorphism
θ(a) = aq
has order
q(µ+1)mkn
. The number of
τ
-periodic classical convolutional
codes has order
q(µ+1)mknτ
, which is much larger. As a result, the search of good periodic time-varying
convolutional codes is much simpler in the class of skew codes in comparison with periodic classical
codes. The search among skew convolutional codes has the same complexity as the search among
fixed classical codes.
How many more skew codes can we obtain by considering all possible automorphisms? Denote
q=ps
, where
p
is the field characteristic then
Fqm=Fpsm =FpM
, i.e., our field
FQ
is an
M
-extension
of the prime field
Fp
. The parameter
q=ps
, we should select such that
Fq
is a subfield of
FpM
, hence
s
should divide
M
. Denote by
δ(M)
the number-of-divisors function that is the number of divisors
i
of
M
, 1
≤i≤M
. Given the field
FQ=FpM
, we can select
q=pi
and the automorphism
θ(a) = aq
in
δ(M)ways.
Lemma 3.
For a fixed field
FQ=FpM
, there are
δ(M)
sub-classes of skew convolutional codes, each defined by
a fixed automorphism θ.
In Example 2, we have
FQ=F22
, i.e.,
p=q=
2,
s=
1,
m=
2.
M=sm =
2 with divisors 1 and 2.
For
i=
1, we have
q=pi=
2 and
θ(a) = a2
considered in Example 2. For
i=
2, we have
q=p2=
4
that corresponds to
θ=id
and gives a constant classical convolutional code. For the field
F6
2
, we have
δ(
6
) =
4, and there are four sub-classes of skew codes with
q=
2
1
, 2
2
, 2
3
, and
q=
2
6
(for fixed code).
4. Properties of Skew Convolutional Codes
4.1. Extension of Fixed Convolutional Codes
To show properties of skew convolutional codes, we will use the following example.
Example 2.
Consider a [2,1] skew convolutional code
b
C
over the field
FQ=Fqm=F22
with automorphism
θ(a) = aq=a2(see Example 1). Let the generator matrix of the code b
Cin polynomial form be
G(D) = (1+αD,α+α2D) = G0+G1D, (22)
where
G0= (1, α),G1= (α,α2). (23)
The generator matrix in scalar form (18) is
G=
1α α α2
1α2α2α
1α α α2
1α2α2α
. . .
. (24)
Here, µ=1; hence, it is a unit memory code. The encoding rule is v =uG, or, from (13), it is
vt=utθt(G0) + ut−1θt−1(G1),t=0, 1, . . . . (25)
In some applications, it is preferable to have a generator matrix in systematic form. For our example,
a systematic fractional matrix can be obtained using the left division of its components by the first component
Gsyst(D) = 1, α+α2D
1+αD=1, (1+αD)−1(α+α2D). (26)
Entropy 2020,22, 1364 8 of 17
Let us show that the matrices
Gsyst(D)
and
G(D)
in
(22)
encode the same code
b
C
. Denote
g1(D) = 1+αD. Then, for any information sequence u(D)∈ Q, we have the code word
u(D)G(D) = u(D)g1(D)g−1
1(D)G(D) = u(D)g1(D)Gsyst(D) = u0(D)Gsyst(D)
and the statement follows since there is a one to one mapping between
u(D)
and
u0(D) = u(D)g1(D)
;
hence, both information sequences u(D)and u0(D)run over all possible causal sequences.
Theorem 2. The class of skew convolutional codes extends the class of fixed convolutional codes.
Proof.
By Lemma 1, the class of fixed codes is included in the class of skew convolutional codes.
Hence, it is sufficient to show that there exists a codeword in a skew convolutional
[n
,
k]
code that
can not belong to any fixed
[n
,
k]
code with the same memory. Indeed, consider the unit memory,
µ=
1, skew
[
2, 1
]
code
b
C
defined by the generator matrix (24). By encoding the information sequence
u=1, 0, 0, 1, we obtain the codeword v=v0,v1,v2,v3,v4= (1, α),(α,α2),(0, 0),(1, α2),(α2,α)∈b
C.
Suppose for the sake of contradiction that the codeword
v
belongs to a fixed unit memory
[
2, 1
]
convolutional code
C0
. A general form of generator matrix of a unit memory fixed
[
2, 1
]
code
C0
is (19):
G0=
a b c d
a b c d
a b c d
a b c d
. . .
where
a
,
b
,
c
,
d
,
∈F22
. Assume that the word
v= (e
,
f
,
g
,
h
,
. . . )G0∈ C0
where
e
,
f
,
g
,
h∈F22
. From
v2=
f(c
,
d) + g(a
,
b) = (
0, 0
)
, it follows that either i)
f=g=
0, or ii) vectors
(c
,
d)
and
(a
,
b)
are
F22
-linearly
dependent. In case i),
v0=e(a
,
b)=(
1,
α)
and
v3=h(a
,
b)=(
1,
α2)
,
e−1(
1,
α) = h−1(
1,
α2)
, which is
impossible since the vectors
(
1,
α)
and
(
1,
α2)
are linearly independent. In case ii), linear combinations
of linearly dependent vectors
(c
,
d)
and
(a
,
b)
should give two linearly independent vectors
v0= (
1,
α)
and v3= (1, α2), which is impossible as well.
4.2. Canonical Encoders and Generator Matrices
The encoder in a controller canonical form [
20
] for the code
b
C
in Example 2with generator
matrix (22) is shown in Figure 2a for even
t
and in Figure 2b for odd
t
. The encoder has one shift
register, since
k=
1. There is one
Q
-ary memory element in the shift register shown as a rectangle,
where
Q=qm=
4 is the order of the field. We need only one memory element since a maximum
degree of items in
G(D)
, which consists of a single row in our example, is 1. A large circle means
multiplication by the coefficient shown inside.
ut−1
+
+
α2
α α
ut
v(1)
t
v(2)
t
(a)
ut−1
+
+
α
α2α2
ut
v(1)
t
v(2)
t
(b)
Figure 2. Encoder of the skew code b
Cfrom Example 2: (a) for even t, (b) for odd t.
Entropy 2020,22, 1364 9 of 17
In the general case of a
k×n
matrix
G(D)
, we define the degree
νi
of its
i
th row as the
maximum degree of its components, and external degree
ν
of
G(D)
is the sum of its row degrees [
21
].
The controller-canonical-form encoder of
G(D)
over
FQ
has
k
shift registers, the
i
th register
has
νi
memory elements, and the total number of
Q
-ary memory elements in the encoder is
ν
.
Different generator matrices for a code Cmay have different external degrees.
Definition 2.
Among all skew polynomial generator matrices (PGM) for a given skew convolutional code
C
,
those for which the external degree is as small as possible are called canonical PGMs. This minimal external
degree is called the degree or overall constraint length of the code C, and denoted as ν=deg C.
4.3. Code Trellises
For the code
b
C
in Example 2, the code trellis is shown in Figure 3. The trellis consists of sections
periodically repeated with period
τ=m=
2. Every section has
Qν=
4
1=
4 states labeled by elements
of the field
FQ
. For the
t
-th section for time
t
,
t=
0, 1,
. . .
, an edge connects the states
ut−1
and
ut
and
is labeled by the code block vt. Every codeword is represented by a path in the trellis that starts from
the zero state 0 and goes to the right. The edge label
vt
is computed according to the encoding rule (25)
as follows:
vt=(ut−1(α,α2) + ut(1, α2)for odd t,
ut−1(α2,α) + ut(1, α)for even t(27)
where we assume that u−1=0, i.e., the initial state of the shift register is 0.
t=0t=1t=2
0
1
α
α2
00
1α
αα2
α21
00
1α
αα2
α21
00
1α2
α1
α2α
α010
Figure 3. Time-varying trellis of the skew code b
C.
4.4. Code Distances
There are two important characteristics of a convolutional code: the free distance
df
and the slope
σ
of the increase of the active burst distance, defined as follows [
20
]. The weight of a branch labeled
by a vector
vt
is defined to be the weight
w(vt)
of
vt
. The weight of a path is the sum of its branch
weights. A path in the trellis that diverges from zero state, which does not use edges of weight 0 from
zero state to zero state, and that returns to zero state after
`
edges is called a loop of length
`
or
`
-loop.
The
`
th order active burst distance
dburst
`
is defined [
20
] to be the minimum weight of
`
-loops in the
code trellis. The slope is defined as σ=lim`→∞dburst
`/`. The free distance is df=min`dburst
`.
Theorem 3
(Singleton bound)
.
The free Hamming distance of
[n
,
k]
skew convolutional code
C
of degree
ν=deg Cis upper bounded as follows:
df≤(n−k)jν
k+1k+ν+1. (28)
Proof. We adopted the proof given in [22] for time-invariant finite state codes. The trellis of the code
C
is time-varying with
Qν
states at every level. Consider
Q`k
information sequences
u0
,
. . .
,
u`−1
of
length
`
blocks. For each of them, the code path in the trellis starts at the state 0 and terminates in one
Entropy 2020,22, 1364 10 of 17
of
Qν
states. From the pigeon-hole principle, it follows that there must be at least
Q`k−ν=QK
of these
paths that have the same final state. The code sequences corresponding to these paths can be thought
of as a block code with length
N=`n
with at least
QK
codewords. We should select
`
such that
K=`k−ν>
0. The Hamming distance
d
of the block code is upper bounded by the Singleton bound
d≤N−K+
1
=`(n−k) + ν+
1. On the other hand,
d
is an upper bound on the free Hamming
distance dfof the code C. Since this is true for all ` > ν/k, we have
df≤min
`:`>ν/k
`(n−k) + ν+1
that gives the upper bound (28).
To obtain (28), we use the Singleton bound for block codes; therefore, the bound (28) is
Singleton-type bound for skew convolutional codes. In fact, this bound and the proof are valid for arbitrary
(also for nonlinear) time-varying trellis codes. In [
23
], codes that reach the Singleton-type bound are
called maximum distance separable (MDS) codes. Any other upper bound for the Hamming distance
of block codes can be used to obtain another upper bound for
df
of skew convolutional codes (also for
time-varying trellis codes). Using the Plotkin bound for block codes, we obtain the following bound.
Corollary 1
(Heller bound)
.
The free Hamming distance of
[n
,
k]
skew convolutional code
C
over
FQ
of degree
ν=deg Cand memory µis upper bounded as follows:
df≤min
i∈b
N$n(µ+i)Qk(µ+i)−ν−1(Q−1)
Qk(µ+i)−ν−1%, (29)
where b
N={1, 2, . . . }if kµ=νand b
N={0, 1, . . . }, otherwise.
The bound is named Heller since it was obtained for fixed binary convolutional codes in 1968,
see [20,24]. The bound (29) is valid for for time-varying (nonlinear or linear) trellis codes.
In the Hamming metric, the upper bound
σ≤n−k(30)
for the slope
σ
was obtained in [
25
] for fixed binary convolutional codes. We conjecture that this bound
is true also for non-binary time-varying convolutional codes, and, hence, for skew convolutional codes.
Another interesting metric for convolutional codes is the sum-rank metric, which can be applied for
multi-shot network coding [
26
]. The metric is defined as follows. The rank weight
wR(vt)
of a vector
vt
over the extension field
Fqm
is the rank of the vector over the base field
Fq
, i.e.,
wR(vt)
is the maximum
number of
Fq
-linearly independent components of
vt
. The sum-rank weight of a sequence
v
in (16)
is the sum of weights of its items
vt
. The sum-rank distance between two sequences is the weight of
their difference.
The rank of a vector
vt∈Fn
qm
is upper bounded by the Hamming weight
wH(vt)
of the vector, i.e.,
wR(vt)≤wH(vt). (31)
Hence, any upper bound for the Hamming metric is an upper bound for the sum-rank metric,
and, from Theorem 3, we have the following corollary.
Corollary 2.
The free sum-rank distance
df
of
[n
,
k]
skew convolutional code
C
of degree
ν=deg C
is upper
bounded by (28) or by (29).
On the other hand, from (31), we obtain the following lemma.
Entropy 2020,22, 1364 11 of 17
Lemma 4.
Let the distance of a code
C
in the sum-rank metric be
d
; then, in the Hamming metric, the code
distance is at least d.
We next compute the free distance, active burst distances, and the slope for the code
b
C
from
Example 2for the Hamming and for the sum-rank metrics.
Lemma 5.
In the sum-rank metric, the skew convolutional code
b
C
defined by
G(D)
in (22) has the
`
-th active
burst distance
dburst
`=`+
2for
`=
2, 3,
. . .
, the slope of the active distance is
σ=
1, and the free distance is
df=4.
Proof. For this code, the shortest length of a loop is `=2; hence, we should consider loops of length
`=
2, 3,
. . .
. It follows from (27) that the weight
wR(vt) = rank vt
of a branch in the code trellis that
diverges from or merges to zero state is 2. A branch connecting two nonzero states has weight at
least 1. Indeed, for odd
t
, the branch label
vt
in (27) is a linear combination of vectors
(α
,
α2)
and
(
1,
α2)
that are
Fqm
-linearly independent, and
vt
can’t be 0 for nonzero coefficients
ut−1
,
ut
. The same
is true for even
t
. Hence,
dburst
`≥`+
2. On the other hand, the path, corresponding to the information
sequence
u0=u1=· · · =u`−16=
0,
u`=
0, is an
`
-loop of weight
`+
2. Hence,
dburst
`≤`+
2, and the
statement of the lemma follows.
Combining Lemmas 3 and 4, we obtain the following corollary.
Corollary 3.
In the Hamming metric, the skew convolutional code
b
C
defined by
G(D)
in (22) has the
`
-th
active burst distance
dburst
`=`+
2for
`=
2, 3,
. . .
, the slope of the active distance is
σ=
1and free distance is
df=4.
For both metrics, the Hamming and the sum-rank, the upper bounds for the free distance (28)
and for the slope (30) for the unit memory [2, 1]code b
Cbecome
df≤2n−k+1=4, and σ≤n−k=1.
Hence, the skew code
b
C
defined by (22) achieves the Singleton-type upper bound on
df
and can
be called MDS codes like in [
23
]. The Heller bound
(29)
gives
df≤
4 as well. The slope of
b
C
also
reaches the upper bound (30).
A generator matrix
G(D)
of a skew convolutional code (and corresponding encoder) is called
catastrophic if there exists an information sequence
u(D)
of infinite weight such that the code sequence
v(D) = u(D)G(D)
has finite weight. The generator matrix
G(D)
in (22) of skew convolutional code
b
C
with
θ= (
.
)q
is non-catastrophic, since the slope
σ>
0. Note that, in case of fixed convolutional
code C0, i.e., for θ=id, the generator matrix (22) is catastrophic, and the code has df=2 and σ=0.
4.5. Blocking of Skew Convolutional Codes
A skew convolutional code
C
, represented as a
τ
-periodic
[n
,
k]
code, can be considered as a
[τn
,
τk]
fixed code
C(τ)
by
τ
-blocking, described in [
21
]. The only difference between
C
and
C(τ)
is
that the code symbols are grouped in blocks
vt
of different lengths in these codes. In this way,
known methods to analyze fixed codes can be applied to skew convolutional codes.
For example, the
[
2, 1
]
skew code
b
C
with generator matrix (24) has period
τ=m=
2 and can be
written as [4, 2]fixed code C(τ)=C(2)defined by the scalar generator matrix
Entropy 2020,22, 1364 12 of 17
G(2)=
1ααα20000
001α α2α0 0
1ααα20000
001α α2α0 0
. . .
which coincides with the matrix
G
in (24) but is written in 2-blocked form. From
G(2)
, we obtain the
generator polynomial matrix of the [4, 2]blocked code b
C(2)as
G(2)(D) = 1α α α2
α2DαD1α!.
In general, for any skew convolutional code
C
and for any
i
-blocking
C(i)
,
i∈N1
, the codewords,
represented by sequences
v
of elements from
Fqm
in (16), are the same for codes
C
and
C(i)
. Hence,
the codes have the same properties, e.g., we have
deg C=deg C(i). (32)
5. Dual Skew Convolutional Codes
5.1. Definitions of Duality
The duality of skew convolutional codes can be defined in different ways.
First, consider a skew convolutional code
C
over
F
in a scalar form as a set of sequences as in (16).
For two sequences
v
and
v0
, where at least one of them is finite, define the scalar product
(v
,
v0)
as the
sum of products of corresponding components, where missing components are assumed to be zeros.
We say that the sequences are orthogonal if (v,v0) = 0.
Definition 3.
The dual code
C⊥
to a skew convolutional
[n
,
k]
code
C
is an
[n
,
n−k]
skew convolutional code
C⊥such that (v,v⊥) = 0for all finite length words v ∈ C and for all words v⊥∈ C⊥.
Another way to define orthogonality is, for example, as follows. Consider two n-words v(D)and
v⊥(D)
over
Qn
. We say that
v⊥(D)
is left-orthogonal to
v(D)
if
v⊥(D)v(D) =
0 and right-orthogonal
if v(D)v⊥(D) = 0. A left dual code to a skew convolutional code Ccan be defined as
C⊥
left ={v⊥∈ Qn:v⊥(D)v(D) = 0 for all v∈ C}.
The dual code C⊥
left is a left submodule of Qn, hence it is a skew convolutional code.
Later on, we consider dual codes according to Definition 3only, since it is more interesting for
practical applications.
5.2. Parity Check Matrices
Given a code
C
with generator matrix
G
, we next show how to find a parity check matrix
H
,
such that GHT=0.
Let a skew
[n
,
k]
code
C
of memory
µ
be defined by a polynomial generator matrix
G(D)
in (12),
which corresponds to the scalar generator matrix
G
in (18). For the dual
[n
,
n−k]
code
C⊥
, we write a
transposed parity check matrix HTof memory µ⊥, similar to classical convolutional codes, as
HT=
HT
0HT
1. . . HT
µ⊥
θ(HT
0). . . θ(HT
µ⊥−1)θ(HT
µ⊥)
. . .
(33)
Entropy 2020,22, 1364 13 of 17
where
rank(H0) = n−k
. Similar to [
20
], we call the matrix
H⊥
the syndrome former and write it in
polynomial form as
HT(D) = HT
0+HT
1D+· · · +HT
µ⊥Dµ⊥. (34)
Then, we have the following parity check matrix of the causal code
C
with the generator matrix (21)
H=
H0
H1θ(H0)
.
.
..
.
.
Hµ⊥θ(Hµ⊥−1).
.
.
θ(Hµ⊥)
(35)
which, in the case of θ=id, coincides with the check matrix of a classical fixed convolutional code.
From Definition 3, we have that
vHT=
0 for all sequences
v∈ C
over
F
. On the other hand,
from (4), we have that every codeword
v(D)∈ C
can be written as
v(D) = u(D)G(D)
. Hence, if we
find an
n×(n−k)
matrix
HT(D)
over
R
of full rank such that
G(D)HT(D) =
0, then every codeword
satisfies
v(D)HT(D) = u(D)G(D)HT(D) =
0 and, vice versa, i.e., if
v(D)HT(D) =
0 then
v(D)
is a
codeword of C.
Theorem 4. We have G(D)HT(D) = 0if and only if GHT=0.
Proof.
We show the proof for the code of memory
µ=
1 (like in Example 2). For the general memory
case, the proof follows similarly. Consider the code with generator matrices
G(D)
and
G
given by (12)
and (18). Let us find a check matrix with memory µ⊥=µ=1. Then, we have
HT(D) = HT
0+HT
1D(36)
and
HT=
HT
0HT
1
θ(HT
0)θ(HT
1)
θ2(HT
0)θ2(HT
1)
. . .
. (37)
From the condition
G(D)HT(D) =
0, we have the following system of equations for unknowns
HT
0,HT
1
G0HT
0=0
G0HT
1+G1θ(HT
0) = 0
G1θ(HT
1) = 0.
(38)
From the condition
GHT=
0, we obtain the following equations: by multiplying the first row of
Gby HTwe get the system (38), by multiplying the second row of of Gby HTwe get the system
θ(G0)θ(HT
0) = 0
θ(G0)θ(HT
1) + θ(G1)θ2(HT
0) = 0
θ(G1)θ2(HT
1) = 0
which is equivalent to (38). Multiplication of other rows of
G
by
HT
does not give new equations.
Hence, conditions G(D)HT(D) = 0 and GHT=0 give the same system (38).
Entropy 2020,22, 1364 14 of 17
Example 3.
For the code
b
C
from Example 2, we write
H0= (a
,
c)
and
H1= (b
,
d)
. Using
G0
,
G1
from (22)
and solving the system (38), we obtain
H0= (α
, 1
)
and
H1= (
1,
α)
. Hence,
H(D) = (α+D
, 1
+αD)
and a
parity check matrix H of the code b
C, which is a generator matrix for the dual code b
C⊥, is as follows:
H=
α1
1α α21
1α2α1.
.
.
1α
.
5.3. Trellises of Dual Codes
Similar to fixed convolutional codes, we have the following theorem:
Theorem 5. For a skew convolutional code Cand its dual C⊥, we have deg C=degC⊥.
Proof.
Denote by
τ
and
τ⊥
periods of the codes
C
and
C⊥
, respectively. Let
`
be the least common
multiple of periods
τ
and
τ⊥
; then, the
`
-blocked codes
C(`)
and
(C⊥)(`)
are both fixed convolutional
codes. The fixed codes
C(`)
and
(C⊥)(`)
are dual to each other, since blocking does not change code
sequences, hence
deg C(`)=deg(C⊥)(`)
, see, e.g., Theorem 2.69, [
20
] for fixed dual convolutional
codes. From (32), we have deg C=C(`), deg C⊥=deg(C⊥)(`), hence deg C=deg C⊥.
It follows from Theorem 5that the number of states at one level of the code trellis (trellis
complexity) is the same for an original code Cand for its dual C⊥and equals Qdeg C.
The trellis of the dual code
b
C⊥
obtained from the matrix
H
in Example 3is shown in Figure 4.
The trellis has
Qdeg b
C=
4
1=
4 states labeled by elements of the set
S={
0, 1,
α
,
α2}
. Every word of
the dual code
b
C⊥
is represented by a path in the trellis that starts from a state
s−1∈ S
and goes to the
right. For the trellis section corresponding to time
t=
0, 1,
. . .
, the edge connecting states
st−1
and
st
are labeled by v⊥
tcomputed as follows:
v⊥
t=(st−1(α2, 1) + st(1, α2)for odd t,
st−1(α, 1) + st(1, α)for even t.
t=0t=1t=2
0
1
α
α2
00
1α
αα2
α21
00
1α
αα2
α21
00
1α2
α1
α2α
αα 11 αα
Figure 4. Time-varying trellis of the dual skew code b
C⊥from Example 3.
6. Trellis Decoding of Skew Convolutional Codes
For a given skew convolutional code
C
, we showed how to obtain a code trellis using a generator
matrix of the code. Another way to obtain a code trellis of
C
using a parity check matrix
H
was
proposed in [
27
]. Having a code trellis, one can use the Viterbi decoder [
4
] for maximum likelihood
sequence decoding or the BCJR decoder [28] for symbol-wise decoding.
Entropy 2020,22, 1364 15 of 17
For an
[n
,
k]
skew convolutional code, the complexity of the Viterbi decoder has order
κ=nQkQdeg C
operations (additions and binary selections), which exponentially increases in
k
and
might be high for high rate codes. Using detailed code trellis [
27
,
29
], where every edge is labeled by a
single field element, the decoding complexity can be reduced to
κ=nQmin{k,n−k}Qdeg C. (39)
Another advantage of the method in [
29
] is that it can be applied to every trellis section separately,
which is convenient for time-varying codes. The decoding complexity of a particular code can also be
decreased using methods in [
30
]. The complexity of the BCJR decoding algorithm has the same order
as in (39) as well.
Symbol-wise decoding of a skew convolutional code Ccan be implemented using a trellis of the
dual code C⊥, see [31–33]. The order of decoding complexity in this case is also given in (39).
7. Conclusions
A new class of non-binary skew convolutional codes was defined that extends the class of fixed
convolutional codes. The skew convolutional codes are equivalent to periodic time-varying classical
convolutional codes but have as compact a description as fixed convolutional codes.
Given a field
F=FpM=Fqm
of characteristic
p
and code parameters
n
,
k
and
µ
; for every
authomorphism
θ(a) = qa
of the field, the subclass
SCC(θ)
of skew convolutional
[n
,
k]
codes of
memory
µ
over the field is defined. All the subclasses have the same number of codes. In case of the
identity automorphism θ=id, we obtain the subclass SCC(id)of classical fixed convolutional codes.
Any other automorphism θof the field gives a subclass SCC(θ)of skew convolutional codes that can
be represented as a periodic time-varying convolutional code with typical period
m
. The total number
of the subclasses
SCC(θ)
is equal to the number of divisors of
M
, which is usually not a large number.
The class of
m
-periodic time-varying convolutional codes is larger than the class of skew convolutional
codes. Every code in the subclass
SCC(θ)
is defined by a
k×n
polynomial generator matrix
G(D)
over the ring of
θ
-skew polynomials; hence, the descriptions of skew codes and fixed codes are the
same, and the description is given by the same matrix G(D).
Every
τ
-periodic convolutional
[n
,
k]
code can be written as a fixed [
τn
,
τk]
code; hence,
skew convolutional codes can be analyzed by methods known for fixed codes. We showed how
to design generator and parity check matrices in polynomial and scalar forms, encoders and code
trellises for skew convolutional codes, and their duals. Using code trellises for original and dual codes,
in the case of channels without memory, one can apply Viterbi or BCJR decoding algorithms, or the
dualized BCJR algorithm.
Future work. We gave just a first encounter with skew convolutional codes. There are many open
problems remaining. The algebraic structure of classical fixed convolutional codes is well understood,
see, e.g., [
20
,
21
] and references therein. The questions such as how to obtain a canonical generator
matrix of a skew convolutional code and its dual, or how to design encoders of a fractional generator
matrix can be considered in the future. Another open problem is to find good skew convolutional
codes reaching an upper bound on the free distance. One possibility to obtain skew convolutional
codes is based on unwrapping skew quasi-cyclic (QC) block codes (see such codes in [
17
]) in a way
similar to [
34
] or [
35
], where it is shown how fixed classical convolutional codes can be obtained by
unwrapping QC block codes and vice versa.
Author Contributions:
Conceptualization, V.S., W.L., O.G. and G.K.; Investigation, V.S., W.L., O.G. and G.K.;
Writing—original draft, V.S., W.L., O.G. and G.K. All authors have read and agreed to the published version of
the manuscript.
Funding:
The work of V. Sidorenko was supported by the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (grant agreement No 801434) and by the Chair of
Communications Engineering at the Technical University of Munich. The work of O. Günlü was supported by the
German Federal Ministry of Education and Research (BMBF) within the national initiative for “Post Shannon
Entropy 2020,22, 1364 16 of 17
Communication (NewCom)” under Grant 16KIS1004. The work of G. Kramer was supported in part by the
German Research Foundation through DFG Grant KR 3517/9-1.
Acknowledgments:
The authors are grateful to the guest editor, to the assistant editor, and especially to
anonymous reviewers for their comments and advice that allowed us to improve the manuscript.
Conflicts of Interest: The authors declare no conflict of interest.
References
1. Elias, P. Coding for noisy channels. IRE Conv. Rec. 1955,4, 37–46.
2.
Fano, R. A heuristic discussion of probabilistic decoding. IEEE Trans. Inf. Theory
1963
,9, 64–74. [CrossRef]
3. Massey, J.L. Threshold Decoding; MIT Press: Cambridge, MA, USA, 1963.
4.
Viterbi, A. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm.
IEEE Trans. Inf. Theory 1967,13, 260–269. [CrossRef]
5.
Berrou, C.; Glavieux, A.; Thitimajshima, P. Near Shannon limit error-correcting coding and decoding:
Turbo-codes. 1. In Proceedings of the ICC ’93—IEEE International Conference on Communications, Geneva,
Switzerland, 23–26 May 1993; Volume 2, pp. 1064–1070. [CrossRef]
6.
IEEE Standard for Telecommunications and Information Exchange between Systems—LAN/MAN Specific
Requirements—Part 11: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications:
High Speed Physical Layer in the 5 GHz Band. Available online: https://ieeexplore.ieee.org/document/
815305 (accessed on 1 December 2020).
7.
Filler, T.; Judas, J.; Fridrich, J. Minimizing Additive Distortion in Steganography Using Syndrome-Trellis
Codes. IEEE Trans. Inf. Forensics Secur. 2011,6, 920–935. [CrossRef]
8.
Ouahada, K. Nonbinary convolutional codes and modified M-FSK detectors for power-line communications
channel. J. Commun. Netw. 2014,16, 270–279. [CrossRef]
9.
Holzbaur, L.; Freij-Hollanti, R.; Wachter-Zeh, A.; Hollanti, C. Private Streaming With Convolutional Codes.
IEEE Trans. Inf. Theory 2020,66, 2417–2429. [CrossRef]
10.
Mooser, M. Some periodic convolutional codes better than any fixed code (Corresp.). IEEE Trans. Inf. Theory
1983,29, 750–751. [CrossRef]
11.
Lee, P.J. There are many good periodically time-varying convolutional codes. IEEE Trans. Inf. Theory
1989
,35,
460–463. [CrossRef]
12. Gabidulin, E.M. Theory of Codes with Maximum Rank Distance. Probl. Inform. Trans. 1985,21, 1–12.
13.
Boucher, D.; Ulmer, F. Coding with skew polynomial rings. J. Symb. Comput.
2009
,44, 1644–1656. [CrossRef]
14.
Boucher, D.; Ulmer, F. Codes as Modules over Skew Polynomial Rings; Springer: Berlin/Heidelberg,
Germany, 2009. [CrossRef]
15. Martínez-Peñas, U. Sum-Rank BCH Codes and Cyclic-Skew-Cyclic Codes. arXiv 2020, arXiv:2009.04949.
16. Gluesing-Luerssen, H. Skew-Polynomial Rings and Skew-Cyclic Codes. arXiv 2019, arXiv:1902.03516.
17.
Abualrub, T.; Ghrayeb, A.; Aydin, N.; Siap, I. On the Construction of Skew Quasi-Cyclic Codes. IEEE Trans.
Inf. Theory 2010,56, 2081–2090. [CrossRef]
18. Ore, O. Theory of Non-Commutative Polynomials. Ann. Math. 1933,34, 480–508. [CrossRef]
19. Clark, P. Non-Commutative Algebra; University of Georgia: Athens, GA, USA, 2012.
20.
Johannesson, R.; Zigangirov, K.S. Fundamentals of Convolutional Coding; John Wiley and Sons, Ltd.: Hoboken,
NJ, USA, 2015.
21.
McEliece, R.J. The Algebraic Theory of Convolutional Codes. In Handbook of Coding Theory; Chapter 12;
Pless, V.S., Huffman, W.C., Eds.; Elsevier Science: Amsterdam, The Netherlands, 1998; Volume I,
pp. 1065–1138.
22.
Pollara, F.; McEliece, R.J.; Abdel-Ghaffar, K. Finite-state codes. IEEE Trans. Inf. Theory
1988
,34, 1083–1089.
[CrossRef]
23.
Rosenthal, J.; Smarandache, R. Maximum Distance Separable Convolutional Codes. Appl. Algebra Eng.
Commun. Comput. 1998,10, 15–32. [CrossRef]
24.
Gluesing-Luerssen, H.; Schmale, W. Distance bounds for convolutional codes and some optimal codes.
arXiv 2003, arXiv:math/0305135.
Entropy 2020,22, 1364 17 of 17
25.
Jordan, R.; Pavlushkov, V.; Zyablov, V.V. An upper bound on the slope of convolutional codes.
In Proceedings of the 2002 IEEE International Symposium on Information Theory, Lausanne, Switzerland,
30 June–5 July 2002; p. 424. [CrossRef]
26.
Wachter-Zeh, A.; Stinner, M.; Sidorenko, V. Convolutional Codes in Rank Metric with Application to
Random Network Coding. IEEE Trans. Inf. Theory 2015,61, 3199–3213. [CrossRef]
27.
Sidorenko, V.; Zyablov, V. Decoding of convolutional codes using a syndrome trellis. IEEE Trans. Inf. Theory
1994,40, 1663–1666. [CrossRef]
28.
Bahl, L.; Cocke, J.; Jelinek, F.; Raviv, J. Optimal decoding of linear codes for minimizing symbol error rate
(Corresp.). IEEE Trans. Inf. Theory 1974,20, 284–287. [CrossRef]
29.
Li, W.; Sidorenko, V.; Jerkovits, T.; Kramer, G. On Maximum-Likelihood Decoding of Time-Varying Trellis
Codes. In Proceedings of the 2019 XVI International Symposium “Problems of Redundancy in Information
and Control Systems” (REDUNDANCY), Moscow, Russia, 21–25 October 2019; pp. 104–109. [CrossRef]
30.
Lafourcade, A.; Vardy, A. Optimal sectionalization of a trellis. IEEE Trans. Inf. Theory
1996
,42, 689–703.
[CrossRef]
31.
Hartmann, C.; Rudolph, L. An optimum symbol-by-symbol decoding rule for linear codes. IEEE Trans.
Inf. Theory 1976,22, 514–517. [CrossRef]
32.
Berkmann, J.; Weiss, C. On dualizing trellis-based APP decoding algorithms. IEEE Trans. Commun.
2002
,50,
1743–1757. [CrossRef]
33.
Srinivasan, S.; Pietrobon, S.S. Decoding of High Rate Convolutional Codes Using the Dual Trellis. IEEE Trans.
Inf. Theory 2010,56, 273–295. [CrossRef]
34.
Esmaeili, M.; Gulliver, T.A.; Secord, N.P.; Mahmoud, S.A. A link between quasi-cyclic codes and
convolutional codes. IEEE Trans. Inf. Theory 1998,44, 431–435. [CrossRef]
35.
Kudryashov, B.D.; Zakharova, T.G. Block Codes from Convolution Codes. Probl. Peredachi Inf.
1989
,25,
98–102.
Publisher’s Note:
MDPI stays neutral with regard to jurisdictional claims in published maps and institutional
affiliations.
©
2020 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access
article distributed under the terms and conditions of the Creative Commons Attribution
(CC BY) license (http://creativecommons.org/licenses/by/4.0/).
