# On the Uncontrollability of Nonabelian Group Codes with Uncoded Groupℤp

Authors: Jorge Pedraza Arpasi
Journal: Mathematical Problems in Engineering
 (2011)

---

## Abstract

Error-correcting encoding is a mathematical manipulation of the information against transmission errors over noisy communications channels. One class of error-correcting codes is the so-calledgroup codes. Presently, there are many good binary group codes which are abelian. A group code is a family of bi-infinite sequences produced by a finite state machine (FSM) homomorphic encoder defined on the extension of two finite groups. As a set of sequences, a group code is a dynamical system and it is known that well-behaved dynamical systems must be necessarily controllable. Thus, a good group code must be controllable. In this paper, we work with group codes defined over nonabelian groups. This necessity on the encoder is because it has been shown that the capacity of an additive white Gaussian noise (AWGN) channel using abelian group codes is upper bounded by the capacity of the same channel using phase shift keying (PSK) modulation eventually with different energies per symbol. We will show that when the trellis section group is nonabelian and the input group of the encoder is a cyclic group with, p elements, p prime, then the group code produced by the encoder is noncontrollable.


---

## Body

## 1. Introduction

Data to be transmitted through a noisy channel may suffer impairments when it arrives to its destination. The most known channel noise is the Gaussian noise, which is modeled as a random signal having a normal probabilistic distribution. The channels suffering Gaussian noise are calledadditive white Gaussian noise—AWGN channels [1–4]. In the landmark paper [5], Shannon showed that there exist methods to encode data against channel noise. One key idea behind an error-correcting code—ECC—is the measure of the channel noise in terms of error probability P(e). For binary data, P(e) of a given physical channel can be obtained empirically. For instance, if after transmitting 1015  bits through the channel we observe that 1015-1 bits were transmitted correctly and one bit was transmitted erroneously, then we can say that the upper bound of P(e), of this channel, is 10-15 or P(e)<10-15. This error probability can be reduced by enhancing the hardware components of the channel or alternatively by using ECC. Mostly the use of ECC on the data to be transmitted is more economic than the enhancing of hardware components of the physical channel. That is why an ECC is important. Classically, the essence of an ECC is the splitting of the information data to be transmitted in packages with constant size, let us say m, then is the added k symbols which are functions of the previous m symbols. After that is transmitted, n=m+k encoded symbols, instead of m. The introduction of the additional k symbols reduces the data rate through the channel. To maintain the original velocity of the data transmission, the physical channel demands either more power or more bandwidth.In 1981, Ungerboeck in [6] introduced a way to encode data against transmission errors, without increasing the consumption of bandwidth by using a technique called set partitioning map. This technique matches the output symbols of a classical binary convolutional encoder and the signal constellation from a phase shift keying—PSK—modulation. Mathematically, the output symbols of a binary convolutional encoder with the modulo-2 addition constitute an abelian group, whereas the PSK constellation constitutes a discrete set of points from a bidimensional vector space isomorphic with the plane ℝ2. Towards to generalize, Ungerboeck’s technique proposed the matching of a generic group Y that could represent the output set of an encoder with a discrete set of points from an Euclidean space ℝn that could represent the signal constellation from ASK (amplitude shift keying), FSK (frequency shift keying), or PSK modulation, [2, 7–9]. In this direction in [7] is introduced the wide sense homomorphic encoder which is a finite state machine (FSM) defined over extension of groups. The bi-infinite outputs of this encoder are the codewords and constitute the group code. But, one important result that motivates our work was given in [8] where it was shown that any AWGN channel using group codes over abelian groups has its capacity upper bounded by some uncoded AWGN channel capacity using PSK modulation. Thus, nonabelian and well-behaved group codes could surmount this PSK limit. In the sense of control theory, a group code is well behaved when it is controllable and observable. Classical group codes over binary groups always are well behaved, that is why there is not any concern about control consideration of these kind of codes. This well behavior also is true for some especial cases of abelian group codes. In the current paper, we deal with nonabelian group codes but we do not construct any new code. Instead of it, we study the class of group codes produced by an FSM encoder with a group S, representing the states of the FSM, inputs group ℤp={0,1,2,…,p-1}, cyclic group of order prime p. Then, our group codes are defined over nonabelian extensions of ℤp by S. For that, this paper is organized as follows.In Section2 is defined the extension of a generic group U by the group S; this extension is denoted as U⊠S. Then is defined the FSM encoder of a group code which also is called ISO (input/state/output) machine. The next state mapping and the encoder (output) mapping are defined over the extension U⊠S. Finally, is defined the group code 𝒞, produced by the FSM encoder, as a family of bi-infinite sequences of outputs.In Section3, the group code 𝒞 is presented as a dynamical system in the sense of [10]. Also, a graphical description of a group code known as a trellis is presented. It is established that the trellis diagram is a set of paths of transitions between states. After given the control definition, a sufficient condition of noncontrollability is made in Theorem 3.4. Also are presented the definition and conditions about parallel transitions that are used directly in our main result.In Section4, we present our original contributions about the noncontrollability of group codes produced by encoders defined on nonabelian extensions ℤp⊠S. The main result of this work, which is Theorem 4.7, states that (a) if ℤp⊠S is nonabelian, with S abelian, then the resulting code will have parallel transitions and (b) if both ℤp⊠S and S are nonabelian then the resulting code will be noncontrollable. Therefore, the extension ℤp⊠S is bad for constructing group codes.


## 2. Group Extensions and Group Codes

### 2.1. Group Extensions

Definition 2.1.
Given a groupG with a normal subgroup N, consider the quotient group G/N. If there are two groups U and S such that U is isomorphic with N and S is isomorphic with G/N, then it is said that G is an extension of U by S [11].We will denote  the extension “U by S” by the symbol U⊠S, also we will use the standard notations U≅N meaning “U is isomorphic with S” and N⊲G meaning “N normal subgroup of G.” When G is an extension U⊠S, each element g∈G can be “factored” as an unique ordered pair (u,s), u∈U and s∈S. The semidirect product U⋊S is a particular case of extension, but also it is known that the semidirect product is a generalization of the direct product U×S. A canonical definition of extension of groups is given in [11, 12]; specially in [12] we find a “practical” way to decompose a given group G, with normal subgroup N, in an extension U⊠S. That decomposition depends on the choice of isomorphisms υ:N→U, ψ:S→G/N and a lifting l:G/N→G such that l(N)=e, the neutral element of G. Then, defining ϕ:S→Aut(U) by(2.1)ϕ(s)(u)=υ[l(ψ(s))⋅υ-1(u)⋅(l(ψ(s)))-1],
and ξ:S×S→U,(2.2)ξ(s1,s2)=l(ψ(s1,s2))l(ψ(s1))l(ψ(s2)),
the decomposition U⊠S with the group operation(2.3)(u1,s1)*(u2,s2)=(u1⋅ϕ(s1)(u2)⋅ξ(s1,s2),s1s2)
is isomorphic with G, that is, g=(u,s).Notice that the resulting pair of(u1,s1)*(u2,s2), of the above operation (2.3), is (u′,s1s2) for some u′∈U and s1s2 is the operation on S. This property allows us to do not be concerned to obtain an explicit result when multiple factors are acting. For instance, in the proof of some Lemmas, it will be enough to say that (u′,s1s2⋯sn) is the resulting pair of the multiple product (u1,s1)*(u2,s2)*(u3,s3)*⋯*(un,sn), where u′ is some element of U. Analogously, (u,s)n=(u′,sn) for some u′∈U.Example 2.2.
Consider the direct product groupℤ23={(x1,x2,x3);xi∈ℤ2}. This abelian group can be decomposed as an extension ℤ2⊠ℤ22.By using the more convenient notation 00 instead of(0,0), 010 instead of  (0,1,0), and so forth, we have that the normal subgroup N={000,100}⊲ℤ23 is isomorphic with ℤ2. The quotient group ℤ23/N = {{000,100},{010,110},{001,101},{111,011}} is isomorphic with ℤ22. Thus, in an expected way, we have shown that ℤ23 is an extension of ℤ2⊠ℤ22.


### 2.2. Finite State Machines and Group Codes

Finite state machines (FSM) are a subject of automata theory.  Arbib in [13] describes a FSM as a quintuple M=(I,S,O,δ,ξ), where I is the inputs alphabet, S is the alphabet of states of the machine, O is the outputs alphabet, δ:I×S→S is the next-state mapping, and ξ:I×S→O is the output mapping. Following [8, 9, 14] and by making modifications on the FSM notation, suitable for our context of group codes, it is given the definition of an encoder as follows.Definition 2.3.
LetU, S, and Y be finite groups. Let ν:U⊠S→S and ω:U⊠S→Y be group homomorphisms defined over an extension U⊠S such that the mapping Ψ:U⊠S→S×Y×S defined by
(2.4)Ψ(u,s)=(s,ω(u,s),ν(u,s))
is injective with ν surjective.
Then, an encoder of a group code is the machineM=(U,S,Y,ν,ω).The groupU is called the uncoded information group and Y is called the encoded information group. To begin working, the encoder needs an initial state s0∈S and a sequence of inputs {ui}i=1n, ui∈U. Then, the encoder will respond with two sequences {si}i=1n, si∈S, and {yi}i=1n, yi∈Y in the following way:(2.5)ν(u1,s0)=s1,ω(u1,s0)=y1,ν(u2,s1)=s2,ω(u2,s1)=y2,ν(u3,s2)=s3,ω(u3,s2)=y3,⋮⋮⋮⋮ν(un,sn-1)=snω(un,sn-1)=yn.
If we agree that the present time is 0 (zero) and the state s0 represents the present state, then the next integer time is 1 (one) and s1 represents the next state from now. Analogously, the next state from s1 will be s2 and generally si will be the next state from si-1. In this way, states with positive indices, {si}i=1n, form a sequence of future states.On the other hand, sinceν is surjective, then must exist at least one pair (u0,s-1) such that s0=ν(u0,s-1). The state s-1 can represent the previous state from the present state s0. Analogously for s-1, there must exist a pair (u-1,s-2) such that ν(u-1,s-2)=s-1 with s-2 representing a previous state from s-1 and so on s-i is one previous state from s{-i+1}. Thus, for a given present state s0, there are sequences of past states {si}i=-n-1, past outputs {yi}i=-n-1, and past inputs {ui}i=-n+10 such that(2.6)ν(u0,s-1)=s0,ω(u0,s-1)=y0,ν(u-1,s-2)=s-1,ω(u-1,s-2)=y-1,ν(u-2,s-3)=s-2,ω(u-2,s-3)=y-2,⋮⋮⋮⋮ν(u{-n+1},s-n)=s{-n+1}ω(u{-n+1},s-n)=y{-n+1}.Therefore, given bi-infinite sequence of inputs{ui}i∈ℤ, ui∈U, and one state s0∈S, the encoder M=(U,S,Y,ν,ω) will response with the sequence {yi}i∈ℤ, yi∈Y, of outputs while its internal states will have the sequence {si}i∈ℤ, si∈S. Notice that once made the choice of one initial state s0, the future relations between the single sequences of inputs and the pair of sequences of outputs and states are bijective, that is, {{uk}i∈ℕ}⇄1-1{{yi}i∈ℕ,{si}i∈ℕ}, where ℕ={1,2,3,…} is the natural numbers set.Definition 2.4.
A time-invariant group code𝒞 is the family of bi-infinite sequences y={yi}i∈ℤ produced by the encoder M=(U,S,Y,ν,ω), with yi=ω(ui,si-1). Each sequence y={yi}i∈ℤ is called a codeword [7–9, 15].Example 2.5.
Consider the encoderM=(ℤ2,ℤ22,ℤ23,ν,ω) where ν:ℤ2⊠ℤ22→ℤ22 defined by ν(u,s1,s2)=(u+s2,s1) and ω:ℤ2⊠ℤ22→ℤ23 is defined by ω(u,s1,s2)=(s2,u,s1).Suppose that the encoder is initialized at states0=00, then for the inputs sequence {1,1,0,0,1,1,0,1,0,1} the encoder states will be {10,11,11,11,01,00,00,10,01,00} and the sequence of encoded outputs will be {010,011,101,101,111,110,000,010,001,110}.


## 2.1. Group Extensions

Definition 2.1.
Given a groupG with a normal subgroup N, consider the quotient group G/N. If there are two groups U and S such that U is isomorphic with N and S is isomorphic with G/N, then it is said that G is an extension of U by S [11].We will denote  the extension “U by S” by the symbol U⊠S, also we will use the standard notations U≅N meaning “U is isomorphic with S” and N⊲G meaning “N normal subgroup of G.” When G is an extension U⊠S, each element g∈G can be “factored” as an unique ordered pair (u,s), u∈U and s∈S. The semidirect product U⋊S is a particular case of extension, but also it is known that the semidirect product is a generalization of the direct product U×S. A canonical definition of extension of groups is given in [11, 12]; specially in [12] we find a “practical” way to decompose a given group G, with normal subgroup N, in an extension U⊠S. That decomposition depends on the choice of isomorphisms υ:N→U, ψ:S→G/N and a lifting l:G/N→G such that l(N)=e, the neutral element of G. Then, defining ϕ:S→Aut(U) by(2.1)ϕ(s)(u)=υ[l(ψ(s))⋅υ-1(u)⋅(l(ψ(s)))-1],
and ξ:S×S→U,(2.2)ξ(s1,s2)=l(ψ(s1,s2))l(ψ(s1))l(ψ(s2)),
the decomposition U⊠S with the group operation(2.3)(u1,s1)*(u2,s2)=(u1⋅ϕ(s1)(u2)⋅ξ(s1,s2),s1s2)
is isomorphic with G, that is, g=(u,s).Notice that the resulting pair of(u1,s1)*(u2,s2), of the above operation (2.3), is (u′,s1s2) for some u′∈U and s1s2 is the operation on S. This property allows us to do not be concerned to obtain an explicit result when multiple factors are acting. For instance, in the proof of some Lemmas, it will be enough to say that (u′,s1s2⋯sn) is the resulting pair of the multiple product (u1,s1)*(u2,s2)*(u3,s3)*⋯*(un,sn), where u′ is some element of U. Analogously, (u,s)n=(u′,sn) for some u′∈U.Example 2.2.
Consider the direct product groupℤ23={(x1,x2,x3);xi∈ℤ2}. This abelian group can be decomposed as an extension ℤ2⊠ℤ22.By using the more convenient notation 00 instead of(0,0), 010 instead of  (0,1,0), and so forth, we have that the normal subgroup N={000,100}⊲ℤ23 is isomorphic with ℤ2. The quotient group ℤ23/N = {{000,100},{010,110},{001,101},{111,011}} is isomorphic with ℤ22. Thus, in an expected way, we have shown that ℤ23 is an extension of ℤ2⊠ℤ22.


## 2.2. Finite State Machines and Group Codes

Finite state machines (FSM) are a subject of automata theory.  Arbib in [13] describes a FSM as a quintuple M=(I,S,O,δ,ξ), where I is the inputs alphabet, S is the alphabet of states of the machine, O is the outputs alphabet, δ:I×S→S is the next-state mapping, and ξ:I×S→O is the output mapping. Following [8, 9, 14] and by making modifications on the FSM notation, suitable for our context of group codes, it is given the definition of an encoder as follows.Definition 2.3.
LetU, S, and Y be finite groups. Let ν:U⊠S→S and ω:U⊠S→Y be group homomorphisms defined over an extension U⊠S such that the mapping Ψ:U⊠S→S×Y×S defined by
(2.4)Ψ(u,s)=(s,ω(u,s),ν(u,s))
is injective with ν surjective.
Then, an encoder of a group code is the machineM=(U,S,Y,ν,ω).The groupU is called the uncoded information group and Y is called the encoded information group. To begin working, the encoder needs an initial state s0∈S and a sequence of inputs {ui}i=1n, ui∈U. Then, the encoder will respond with two sequences {si}i=1n, si∈S, and {yi}i=1n, yi∈Y in the following way:(2.5)ν(u1,s0)=s1,ω(u1,s0)=y1,ν(u2,s1)=s2,ω(u2,s1)=y2,ν(u3,s2)=s3,ω(u3,s2)=y3,⋮⋮⋮⋮ν(un,sn-1)=snω(un,sn-1)=yn.
If we agree that the present time is 0 (zero) and the state s0 represents the present state, then the next integer time is 1 (one) and s1 represents the next state from now. Analogously, the next state from s1 will be s2 and generally si will be the next state from si-1. In this way, states with positive indices, {si}i=1n, form a sequence of future states.On the other hand, sinceν is surjective, then must exist at least one pair (u0,s-1) such that s0=ν(u0,s-1). The state s-1 can represent the previous state from the present state s0. Analogously for s-1, there must exist a pair (u-1,s-2) such that ν(u-1,s-2)=s-1 with s-2 representing a previous state from s-1 and so on s-i is one previous state from s{-i+1}. Thus, for a given present state s0, there are sequences of past states {si}i=-n-1, past outputs {yi}i=-n-1, and past inputs {ui}i=-n+10 such that(2.6)ν(u0,s-1)=s0,ω(u0,s-1)=y0,ν(u-1,s-2)=s-1,ω(u-1,s-2)=y-1,ν(u-2,s-3)=s-2,ω(u-2,s-3)=y-2,⋮⋮⋮⋮ν(u{-n+1},s-n)=s{-n+1}ω(u{-n+1},s-n)=y{-n+1}.Therefore, given bi-infinite sequence of inputs{ui}i∈ℤ, ui∈U, and one state s0∈S, the encoder M=(U,S,Y,ν,ω) will response with the sequence {yi}i∈ℤ, yi∈Y, of outputs while its internal states will have the sequence {si}i∈ℤ, si∈S. Notice that once made the choice of one initial state s0, the future relations between the single sequences of inputs and the pair of sequences of outputs and states are bijective, that is, {{uk}i∈ℕ}⇄1-1{{yi}i∈ℕ,{si}i∈ℕ}, where ℕ={1,2,3,…} is the natural numbers set.Definition 2.4.
A time-invariant group code𝒞 is the family of bi-infinite sequences y={yi}i∈ℤ produced by the encoder M=(U,S,Y,ν,ω), with yi=ω(ui,si-1). Each sequence y={yi}i∈ℤ is called a codeword [7–9, 15].Example 2.5.
Consider the encoderM=(ℤ2,ℤ22,ℤ23,ν,ω) where ν:ℤ2⊠ℤ22→ℤ22 defined by ν(u,s1,s2)=(u+s2,s1) and ω:ℤ2⊠ℤ22→ℤ23 is defined by ω(u,s1,s2)=(s2,u,s1).Suppose that the encoder is initialized at states0=00, then for the inputs sequence {1,1,0,0,1,1,0,1,0,1} the encoder states will be {10,11,11,11,01,00,00,10,01,00} and the sequence of encoded outputs will be {010,011,101,101,111,110,000,010,001,110}.


## 3. Control and Group Codes

Each codeword of a group code satisfies the definition of a trajectory of a dynamical system in the sense of Polderman and Willems [10]. From this, each group code 𝒞 is a dynamical system. In this context, the encoder M=(U,S,Y,ν,ω) is a realization of 𝒞 [8, 9, 16].Given a codewordy and a set of consecutive indices {i,i+1,…,j-1,j}=[i,j], the projection of the codeword over these indices will be y|[i,j]={yi,yi+1,…,yj}. Analogously, y|[i,j)={yi,yi+1,…,yj-1}, y|[i,+∞)={yi,yi+1,…}, and so on. With this notation, the concatenation of two codewords y1, y2∈𝒞 in the instant j is a sequence y1∧jy2 defined by(3.1)y1∧jy2|(-∞,j)=y1|(-∞,j),y1∧jy2|[j,+∞)=y2|[j,+∞).Definition 3.1.
IfL is an integer greater than one, then a group code 𝒞 is said L-controllable if, for any pair of codewords y1 and y2, there are a codeword y3 and one integer k such that the concatenation y1∧ky3∧k+Ly2 is a codeword of the group code 𝒞 [7, 10, 15].It is said that a natural numberl>1 is the index of controllability of a group code 𝒞 when l=min{L;𝒞isL-controllable}. Any applicable group code, for correction of errors of transmission and storage of information, needs to have an index of controllability. Shortly, when a code has an index of controllability, then it is said that it is controllable [10]. Clearly, a code 𝒞 to be L-controllable is a sufficient condition for 𝒞 to be controllable.


### 3.1. Trellis of a Group Code

The triplets(s,ω(u,s),ν(u,s)) of the set {Ψ(u,s)}(u,s)∈U⊠S, where Ψ is defined by (2.4), can be represented graphically. In the context of graph theory [17], they are called edges whose vertexes set is S and the graph is called state diagram labeled by ω(u,s). In Figure 1, the full state diagram of the code generated by the FSM M=(ℤ2,ℤ22,ℤ23,ν,ω), from Example 2.5, is shown between the times 2 and 3; also it is repeated between the times 3 and 4 and so on until times 4 and 5. In the context of coding theory the elements of {Ψ(u,s)}(u,s)∈U⊠S are called transitions or branches. The expansion in time of the state diagram is called trellis diagram. This is made by concatenating at each time unit separate state diagram. For two consecutive time units i and i+1, the transitions bi=(si,ω(ui+1,si),ν(ui+1,si)) and bi+1=(si+1,ω(ui+2,si+1),ν(ui+2,si+1)) are said concatenated when si+1=ν(ui+1,si). Hence, a bi-infinite trellis path of transitions is a sequence b={bi}i∈ℤ such that bi and bi+1 are concatenated for each i∈ℤ. The set of trellis paths form the trellis diagram. Since each codeword y passes only by one state s at each unit of time, the relation between the codewords y and paths b is bijective. Again from Example 2.5, consider the inputs sequence {ui}i∈ℤ, such that u1=1, u2=1, u3=0, u4=0, u5=1, u6=1, and ui=0 for all i∈ℤ-{1,2,3,4,5,6}. The response path b={bi}i∈ℤ is such that b0=(00,010,10), b1=(10,011,11), b2=(11,101,11), b3=(11,101,11), b4=(11,111,01), b5=(01,110,00), and bi=(00,000,00) for all i∈ℤ-{0,1,2,3,4,5}. This response path is shown by a traced line in Figure 1.Figure 1
Trellis diagram of the encoderM=(ℤ2,ℤ22,ℤ23,ν,ω).Definition 3.2.
Two statess and r are said to be connected when there are a path b and indices i,j∈ℤ such that b|[i,j]={bi,bi+1,…,bj} with bi=(si,ω(ui+1,si),ν(ui+1,si)) and bj=(sj,ω(uj+1,sj),ν(uj+1,sj)) such that s=si and r=ν(uj+1,sj).Theorem 3.3.
Let𝒞 be a group code produced by the encoder M=(U,S,Y,ν,ω). If there are two states s∈S and r∈S for which there is no a finite path of transitions connecting them, then 𝒞 is noncontrollable.Proof.
On contrary, there isl>1 such that l is the controllability index of 𝒞. Let y1 be one codeword passing by the state s at time k; let y2 be a codeword passing by the state r at time k+L, L≥l. There must exist y3∈𝒞 with its respective path b3 such that y3|(-∞,k)=y1|(-∞,k) and y3|[k+L,+∞)=y2|[k+L,+∞) and b3|(k,k+L], a finite path, connecting s and r, a contradiction.Equivalently, we can say that two statess and r are connected when there is a finite sequence of inputs {ui}i=1n such that(3.2)r=ν(un,ν(un1,…ν(u2,ν(u1,s))⋯)).Theorem 3.4.
Given an encoder(U,S,Y,ν,ω), consider the family of state subsets {Si}, recursively defined by
(3.3)S0={e},⋮⋮⋮Si={ν(u,s);u∈U,s∈Si-1},i≥0⋮=⋮
then (1)
eachSi is a subgroup of S,(2)
Si-1 is normal in Si, for all i∈{1,2,…},(3)
ifSi-1=Si, then Si=Si+1,(4)
if the group code is controllable, thenS=Sk for some k.Proof.
(1) Considerr,s∈Si. Since ν is surjective, there exist (u1,s1) and (u2,s2) with s1,s2∈Si-1 and u1,u2∈U such that r=ν(u1,s1) and s=ν(u2,s2). Hence, sr=ν(u1,s1)*ν(u2,s2)=ν(u3,s1s2), u3∈U and thus sr∈Si.
(2)  Clearly,S0⊲S1. For i>1, suppose that  Sj-1⊲Sj, for all j≤i. Given s∈Si+1 and r∈Si, consider s·r·s-1=ν(u,s1)*ν(v,r1)*ν(u,s1)-1, where s1∈Si, r1∈Si-1, u,v∈U. Hence, s·r·s-1=ν(u1,r1·s1·r1-1)∈Si, because r1·s1·r1-1∈Si-1.
(3)  Givens∈Si+1, there are r∈Si and u∈U such that ν(u,r)=s. Since Si=Si-1, r∈Si-1. Hence, ν(u,r)=s∈Si.
(4) If not, then there iss∈S such that s∉Sk for any k∈ℕ. Then, the neutral state e∈Sk⊂S and s are not connected by any finite trellis path. Therefore, the group code is noncontrollable.In Figure1  S0={00}, S1={00,10}, S2={00,10,01,11}=S, therefore the code is controllable.Definition 3.5.
Two different transitions(s1,ω(u1,s1),ν(u1,s1)) and (s2,ω(u2,s2),ν(u2,s2)) are parallels if s1=s2 and ν(u1,s1)=ν(u2,s2) and ω(u1,s1)≠ω(u2,s2).The Hamming distancedH(y1,y2) between two codewords y1={yi1}i∈ℤ and y2={yi2}i∈ℤ is defined as the number of components which are different. The minimal distance of a group code is(3.4)dmin⁡=min⁡{dH(y1,y2);y1,y2aredifferentcodewords}.
One desirable property of a group code is a high dmin; the greater dmin, the better the capability to correction of errors. Clearly, when the trellis of a group code has parallel transitions, then dmin=1 and therefore a group code with parallel transitions will not be a good group code.Lemma 3.6.
Consider an encoder(U,S,Y,ν,ω). Let B+ and B- be subsets of the trellis section group {Ψ(u,s)}(u,s)∈U⊠S such that B+={(e,ω(u,e),ν(u,e);u∈U}, the transitions outcoming from the neutral state {e}, and B-={(s,ω(u,s),ν(u,s);ν(u,s)=e}, the transitions incoming into the neutral state {e}. Also, let H+ and H- be subsets of U⊠S such that H+=U⊠{e}={(u,e);u∈U} and H-=Ker(ν)={(u,s);ν(u,s)=e}, then (1)
H+≅B+ and H-≅B-,(2)
bothH+ and H- are normal subgroups of U⊠S,(3)
ifH+∩H-≠{(e,e)}, then {Ψ(u,s)}(u,s)∈U⊠S has parallel transitions,(4)
ifU⊠S is nonabelian and the states group S is abelian, then {Ψ(u,s)}(u,s)∈U⊠S has parallel transitions.Proof.
(1) We haveB+=Ψ(H+) and B+=Ψ(H+), where Ψ is defined in (2.4).
(2) Immediate.
(3) There exists(u,e)∈H+∩H-, with u≠e such that ν(u,e)=e. Since Ψ of (2.4) is injective, ω(u,e)≠e. Therefore, the transitions (e,ω(e,e),ν(e,e)) and (e,ω(u,e),ν(u,e)) are parallels.
(4) The states groupS being abelian implies that G/H+≅G/H- are abelian factor groups. Then, the commutators subgroup (U⊠S)′ is a subgroup of H+∩H-. But U⊠S is nonabelian, then (U⊠S)′≠{(e,e)}. Therefore, from the above item (2.3), {Ψ(u,s)}(u,s)∈U⊠S has parallel transitions.


## 3.1. Trellis of a Group Code

The triplets(s,ω(u,s),ν(u,s)) of the set {Ψ(u,s)}(u,s)∈U⊠S, where Ψ is defined by (2.4), can be represented graphically. In the context of graph theory [17], they are called edges whose vertexes set is S and the graph is called state diagram labeled by ω(u,s). In Figure 1, the full state diagram of the code generated by the FSM M=(ℤ2,ℤ22,ℤ23,ν,ω), from Example 2.5, is shown between the times 2 and 3; also it is repeated between the times 3 and 4 and so on until times 4 and 5. In the context of coding theory the elements of {Ψ(u,s)}(u,s)∈U⊠S are called transitions or branches. The expansion in time of the state diagram is called trellis diagram. This is made by concatenating at each time unit separate state diagram. For two consecutive time units i and i+1, the transitions bi=(si,ω(ui+1,si),ν(ui+1,si)) and bi+1=(si+1,ω(ui+2,si+1),ν(ui+2,si+1)) are said concatenated when si+1=ν(ui+1,si). Hence, a bi-infinite trellis path of transitions is a sequence b={bi}i∈ℤ such that bi and bi+1 are concatenated for each i∈ℤ. The set of trellis paths form the trellis diagram. Since each codeword y passes only by one state s at each unit of time, the relation between the codewords y and paths b is bijective. Again from Example 2.5, consider the inputs sequence {ui}i∈ℤ, such that u1=1, u2=1, u3=0, u4=0, u5=1, u6=1, and ui=0 for all i∈ℤ-{1,2,3,4,5,6}. The response path b={bi}i∈ℤ is such that b0=(00,010,10), b1=(10,011,11), b2=(11,101,11), b3=(11,101,11), b4=(11,111,01), b5=(01,110,00), and bi=(00,000,00) for all i∈ℤ-{0,1,2,3,4,5}. This response path is shown by a traced line in Figure 1.Figure 1
Trellis diagram of the encoderM=(ℤ2,ℤ22,ℤ23,ν,ω).Definition 3.2.
Two statess and r are said to be connected when there are a path b and indices i,j∈ℤ such that b|[i,j]={bi,bi+1,…,bj} with bi=(si,ω(ui+1,si),ν(ui+1,si)) and bj=(sj,ω(uj+1,sj),ν(uj+1,sj)) such that s=si and r=ν(uj+1,sj).Theorem 3.3.
Let𝒞 be a group code produced by the encoder M=(U,S,Y,ν,ω). If there are two states s∈S and r∈S for which there is no a finite path of transitions connecting them, then 𝒞 is noncontrollable.Proof.
On contrary, there isl>1 such that l is the controllability index of 𝒞. Let y1 be one codeword passing by the state s at time k; let y2 be a codeword passing by the state r at time k+L, L≥l. There must exist y3∈𝒞 with its respective path b3 such that y3|(-∞,k)=y1|(-∞,k) and y3|[k+L,+∞)=y2|[k+L,+∞) and b3|(k,k+L], a finite path, connecting s and r, a contradiction.Equivalently, we can say that two statess and r are connected when there is a finite sequence of inputs {ui}i=1n such that(3.2)r=ν(un,ν(un1,…ν(u2,ν(u1,s))⋯)).Theorem 3.4.
Given an encoder(U,S,Y,ν,ω), consider the family of state subsets {Si}, recursively defined by
(3.3)S0={e},⋮⋮⋮Si={ν(u,s);u∈U,s∈Si-1},i≥0⋮=⋮
then (1)
eachSi is a subgroup of S,(2)
Si-1 is normal in Si, for all i∈{1,2,…},(3)
ifSi-1=Si, then Si=Si+1,(4)
if the group code is controllable, thenS=Sk for some k.Proof.
(1) Considerr,s∈Si. Since ν is surjective, there exist (u1,s1) and (u2,s2) with s1,s2∈Si-1 and u1,u2∈U such that r=ν(u1,s1) and s=ν(u2,s2). Hence, sr=ν(u1,s1)*ν(u2,s2)=ν(u3,s1s2), u3∈U and thus sr∈Si.
(2)  Clearly,S0⊲S1. For i>1, suppose that  Sj-1⊲Sj, for all j≤i. Given s∈Si+1 and r∈Si, consider s·r·s-1=ν(u,s1)*ν(v,r1)*ν(u,s1)-1, where s1∈Si, r1∈Si-1, u,v∈U. Hence, s·r·s-1=ν(u1,r1·s1·r1-1)∈Si, because r1·s1·r1-1∈Si-1.
(3)  Givens∈Si+1, there are r∈Si and u∈U such that ν(u,r)=s. Since Si=Si-1, r∈Si-1. Hence, ν(u,r)=s∈Si.
(4) If not, then there iss∈S such that s∉Sk for any k∈ℕ. Then, the neutral state e∈Sk⊂S and s are not connected by any finite trellis path. Therefore, the group code is noncontrollable.In Figure1  S0={00}, S1={00,10}, S2={00,10,01,11}=S, therefore the code is controllable.Definition 3.5.
Two different transitions(s1,ω(u1,s1),ν(u1,s1)) and (s2,ω(u2,s2),ν(u2,s2)) are parallels if s1=s2 and ν(u1,s1)=ν(u2,s2) and ω(u1,s1)≠ω(u2,s2).The Hamming distancedH(y1,y2) between two codewords y1={yi1}i∈ℤ and y2={yi2}i∈ℤ is defined as the number of components which are different. The minimal distance of a group code is(3.4)dmin⁡=min⁡{dH(y1,y2);y1,y2aredifferentcodewords}.
One desirable property of a group code is a high dmin; the greater dmin, the better the capability to correction of errors. Clearly, when the trellis of a group code has parallel transitions, then dmin=1 and therefore a group code with parallel transitions will not be a good group code.Lemma 3.6.
Consider an encoder(U,S,Y,ν,ω). Let B+ and B- be subsets of the trellis section group {Ψ(u,s)}(u,s)∈U⊠S such that B+={(e,ω(u,e),ν(u,e);u∈U}, the transitions outcoming from the neutral state {e}, and B-={(s,ω(u,s),ν(u,s);ν(u,s)=e}, the transitions incoming into the neutral state {e}. Also, let H+ and H- be subsets of U⊠S such that H+=U⊠{e}={(u,e);u∈U} and H-=Ker(ν)={(u,s);ν(u,s)=e}, then (1)
H+≅B+ and H-≅B-,(2)
bothH+ and H- are normal subgroups of U⊠S,(3)
ifH+∩H-≠{(e,e)}, then {Ψ(u,s)}(u,s)∈U⊠S has parallel transitions,(4)
ifU⊠S is nonabelian and the states group S is abelian, then {Ψ(u,s)}(u,s)∈U⊠S has parallel transitions.Proof.
(1) We haveB+=Ψ(H+) and B+=Ψ(H+), where Ψ is defined in (2.4).
(2) Immediate.
(3) There exists(u,e)∈H+∩H-, with u≠e such that ν(u,e)=e. Since Ψ of (2.4) is injective, ω(u,e)≠e. Therefore, the transitions (e,ω(e,e),ν(e,e)) and (e,ω(u,e),ν(u,e)) are parallels.
(4) The states groupS being abelian implies that G/H+≅G/H- are abelian factor groups. Then, the commutators subgroup (U⊠S)′ is a subgroup of H+∩H-. But U⊠S is nonabelian, then (U⊠S)′≠{(e,e)}. Therefore, from the above item (2.3), {Ψ(u,s)}(u,s)∈U⊠S has parallel transitions.


## 4. Nonabelian Group Codes withℤp as information Group Are Not Good

By using group extension of groups, subgroup of commutators, Theorem3.4, and other group theory ideas, we show here that we must search for good nonabelian group codes outside the extension ℤp⊠S.Definition 4.1.
Given a finite groupG and a subgroup H⊂G, the index of H in G, denoted by [G:H], is the number of different cosets of H in G.If|G|,|H| denote the orders of G and H, respectively, then [G:H]=|G|/|H|. It is possible to represent graphically this index such as in Figure 2 where is represented the index [ℤp⊠S1:ℤp⊠S0]. We see that if S1=S0, then [ℤp⊠S1:ℤp⊠S0]=1, and if S1≠S0 then [ℤp⊠S1:ℤp⊠S0]=p.The intersection(ℤp⊠S1)∩(ℤp⊠S)′ when ℤp⊠S0⊂(ℤp⊠S)′.
(a)
IfS1=S0(b)
IfS1≠S0Definition 4.2.
Given a groupG, the group of commutators of G is the subgroup G′={aba-1b-1;a,b∈G}.Lemma 4.3.
Letℤp⊠S be an extension which is a p-group. If ℤp⊠S0⊂(ℤp⊠S)′, then ℤp⊠Si⊂(ℤp⊠S)′, and Si⊂S′, for each i≥1.Proof.
Sinceν is a group homomorphism, the image ν(ℤp⊠S0)=S1 is in the commutators subgroup S′ of S. If S1=S0, then the lemma holds trivially (Figure 2(a)). If S1≠S0, then by the long commutators theorem from [18], there are s∈(S1-S0) and a1,a2,…,at∈S such that s=a1a2⋯ata1-1a2-1⋯at-1. Now, consider u∈ℤp and {u1,u2,…,ut}⊂ℤp such that (u,s)=(u1,a1)*(u2,a2)*⋯*(ut,at)*(u1,a1)-1*(u2,a2)-1*⋯*(ut,at)-1. We have (u,s)∈(ℤp⊠S)′ and (u,s)∉ℤp⊠S0. Therefore, ℤp⊠S1⊂(ℤp⊠S)′ (Figure 2(b)).
Again, sinceν is a group homomorphism, ν(ℤp⊠S1)=S2 is in the commutators subgroup S′ of S. Then, with very similar arguments, we can proof that if S2≠S1, then (ℤp⊠S2)⊂(ℤp⊠S)′ and ν(ℤp⊠S2)=S3⊂S′. Continuing in the same way, we conclude that (ℤp⊠S)′ and Si⊂S′, for any i≥1.Lemma 4.4.
Letℤp⊠S be an extension which is a p-group. Consider the subgroups {Si} defined in (3.3). Then, for each i, either each Si is abelian or Si⊂S′.Proof.
SinceS1 is cyclic and S2 has at most order p2, we have that both S1 and S2 are abelian. Then, let i≥2 be such that S1,S2,…,Si are all abelian with Si+1 nonabelian. Then, there are s1,s2∈Si+1 such that s1s2≠s2s1. Also, there must be u1,u2∈ℤp and r1,r2∈Si, with r1r2=r2r1, such that s1=ν(u1,r1) and s2=ν(u2,r2). Then,
(4.1)s1s2≠s2s1,ν(u1,r1)*ν(u2,r2)≠ν(u2,r2)*ν(u1,r1),ν((u1,r1)*(u2,r2)*(u1,r1)-1*(u2,r2)-1)≠e,ν(u′,r1r2r1-1r2-1)≠e,forsomeu′∈Zp,ν(u′,e)≠e.
From this, u′≠e and (u′,e)∈(ℤp⊠S)′∩(ℤp⊠S0). Since the order of ℤp⊠S0 is p, we have that ℤp⊠S0⊂(ℤp⊠S)′. By Lemma 4.3, (ℤp⊠Si)⊂(ℤp⊠S)′ and Si⊂S′, for each i. Therefore, either Si is abelian or Si⊂S′.Suppose now that we do not have the information about the order ofℤp⊠S; that is, we cannot use the hypothesis that ℤp⊠S is a p-group. In this case, we need to consider S as a generic and finite group. By looking back, again, the family {Si} defined by (3.3), we will show that when U=ℤp, each Si must be a p-group. In that direction, we need to consider the subgroup H- of Lemma 3.6 and from this the second projection of the kernel of ν:(4.2)Sd={s∈S;ν(u,s)=eforsomeu∈Zp}.
Clearly, Sd is a normal subgroup of S and it is isomorphic to ℤp and we have the following lemma.Lemma 4.5.
Consider the encoderM=(ℤp,S,Y,ν,ω). Also, consider the subgroup Sd defined in (4.2), then (1)
if there ares≠e and s∈Sd∩Si, then Sd⊂Si, for i≥0,(2)
ifSd⊂Si, then ν(ℤp,Sd)⊂Si, for i≥0.Proof.
(1) Sincep∈Sd∩Si, then {s,s2,…,sp-1,sp=e}⊂Sd∩Si.
(2) Givenr≠e such that r∈Si∩Sd, suppose there is some u∈ℤp such that ν(u,r)=s∉Si. For the subgroup S1={s0,s1=ν(u1,e),s2=ν(u2,e),…,sp-1=ν(up-1,e)}, we have that sS1 is a coset where each element is ν(u,r)ν(ui,e)=ν(u′,r), for some u′∈ℤp. Hence sS1={ν(ℤp,r)} with sS1∩Si=∅. But, since r∈Sd, there is at least one u0∈ℤp such that ν(u0,r)=e, in contradiction with sS1∩Si=∅.Theorem 4.6.
Consider the encoderM=(ℤp,S,Y,ν,ω), where p is prime. Then, each Si of (3.3) must be a p-group.Proof.
By induction overi, for i=1 we have [S1:S0]=p or [S1:S0]=1. Now, suppose that there is a natural number k>1 such that [Si:Si-1]=p, for all i≤k. We have that the subgroup Sk has pk elements and each of its elements has order pi, i≤k. If p>[Sk+1:Sk]>1, then [Sk+1:Sk]=m=q1r1q2r2⋯qtrt, where each qi is a prime and qi<p. There must be an element s∈(Sk+1-Sk) such that sq1=e.
Letu∈ℤp and r∈Sk be such that ν(u,r)=s, then ν(u1,rq1)=e. Hence, rq1∈Sd∩Sk.
Ifr≠e, then rq1≠e, because q1<p. By Lemma 4.5, Sd⊂Sk and ν(u,r)=s∈Sk, a contradiction.
Ifr=e, then ν(u,r)=s∈S1⊂Sk, a contradiction.Theorem 4.7.
Consider the encoderM=(ℤp,S,Y,ν,ω), where ℤp⊠S is nonabelian and p is a positive prime, then (1)
ifS is abelian, then the group code has bad minimal Hamming distance;(2)
ifS is nonabelian, then the group code is noncontrollable.Proof.
(1) By Lemma3.6, the group code has parallel transitions and by (3.4) has dmin=1.
(2) IfS is not a p-group, then by Theorem 4.6 the resulting code is noncontrollable. If S is a p-group, then ℤp⊠S is also a p-group, then by Lemma 4.4  S is abelian, a contradiction.


## 5. Conclusion

We have shown that there are no controllable group codes defined on the nonabelian extensionℤp⊠S, with p prime and for any finite nonabelian group S. When S is abelian, the group code will have parallel transitions and therefore distance limitations. In contrast, for the cases ℤ22⊠S and (ℤ2)2⊠S, there are important examples of controllable and nonabelian group codes such as the Wei code [19] which has a trellis section isomorphic to the nonabelian 2-group (ℤ2)2⋊D8, where D8 is the symmetries of the square and the symbol ⋊ denotes the semidirect product. This provides a strong clue about the controllability of some p-groups with information groups ℤpn or (ℤp)n.



---

*Source: 783516-2011-12-06.xml*