{'fraction_non_alphanumeric': 0.06187740856540391, 'fraction_numerical': 0.01914733755059502, 'mean_word_length': 3.512248468941382, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the MacWilliams Identity for Convolutional Codes

The adjacency matrix associated with a convolutional code collects in a detailed manner information about the weight distribution of the code. A MacWilliams Identity Conjecture, stating that the adjacency matrix of a code fully determines the adjacency matrix of the dual code, will be formulated, and an explicit formula for the transformation will be stated. The formula involves the MacWilliams matrix known from complete weight enumerators of block codes. The conjecture will be proven for the class of convolutional codes where either the code itself or its dual does not have Forney indices bigger than one. For the general case the conjecture is backed up by many examples, and a weaker version will be established.


Introduction
Two of the most famous results in block code theory are MacWilliams' Identity Theorem and Equivalence Theorem [12], [13]. The first one relates the weight enumerator of a block code to that of its dual code. The second one states that two isometric codes are monomially equivalent. The impact of these theorems for practical as well as theoretical purposes is well-known, see for instance [14,Ch. 11.3, Ch. 6.5, Ch. 19.2] or the classification of constant weight codes in [7,Thm. 7.9.5].
The paramount importance of the weight function in coding theory makes an understanding of weight enumerators, isometries, and, more explicitly, possible versions of the MacWilliams Theorems a must for the analysis of any class of codes. For instance, after realizing the relevance of block codes over finite rings, both theorems have seen generalizations to this class of codes, see for instance [22] and [2]. For convolutional codes the question of a MacWilliams Identity Theorem has been posed already about 30 years ago. In 1977 Shearer/McEliece [20] considered the weight enumerator for convolutional codes as introduced by Viterbi [21]. It is a formal power series in two variables counting the number of irreducible ("atomic") codewords of given weight and length; for the coding-theoretic relevance see, e. g., [21,Sec. VII] and [9,Sec. 4.3]. Unfortunately, a simple example in [20] made clear that a MacWilliams Identity does not exist for these objects. A main step forward has been made in 1992 when Abdel-Ghaffar [1] considered a more refined weight counting object: the weight enumerator state diagram. For unit constraint-length codes he derives a MacWilliams Identity in form of a list of separate formulas relating the labels of this diagram to those of the dual code.
In this paper we will present a MacWilliams Identity for the class of convolutional codes where either the code or its dual does not have Forney indices bigger than one. Duality of codes will be defined in the standard way based on the vanishing of the canonical bilinear form on F[z] n . Our result generalizes not only the block code case, but also Abdel-Ghaffar's transformation for unit constraint-length codes. We will show in Section 6 that the list of identities given in [1] can be written in closed form just like in our MacWilliams Identity. In addition to the result just mentioned we will also formulate an explicit conjecture on a MacWilliams Identity for all classes of convolutional codes. It is backed up by a wealth of examples, and a weaker version will be proven.
The weight counting object in our considerations is the so-called adjacency matrix of the encoder. This matrix has been discussed in detail by McEliece [17], but appears already in different notations earlier in the literature. Indeed, one can show that it basically coincides with the labels of the weight enumerator state diagram as considered in [1]. The adjacency matrix is defined via a state space description of the encoder as introduced in [15]. In this sense our approach follows a series of papers where system theoretic methods have been used successfully in order to investigate convolutional codes, see for instance [18], [19], [3], and [8]. The matrix is labeled by the set of all state pairs, and each entry contains the weight enumerator of all outputs associated with the corresponding state pair. The whole matrix contains considerably more detailed information about the code than the weight enumerator discussed above. Indeed, it is well-known [17], [5] how to derive the latter from the adjacency matrix. Furthermore, in [5] it has been shown that, after factoring out the group of state space isomorphisms, the adjacency matrix turns into an invariant of the code, called the generalized adjacency matrix.
The main outline of our arguments is as follows. In the next section we will introduce two block codes canonically associated with a convolutional code. They are crosswise dual to the corresponding block codes of the dual convolutional code. Later on this fact will allow us to apply the MacWilliams Identity for block codes suitably. Indeed, in Section 3 we will introduce the adjacency matrix Λ and show that its nontrivial entries are given by the weight enumerators of certain cosets of these block codes. The main ingredient for relating Λ with the adjacency matrix of the dual will be a certain transformation matrix H as it also appears for the complete weight enumerator of block codes. This matrix will be studied in Section 4, and a first application to the adjacency matrix will be carried out. In Section 5 we will be able to show our main results. Firstly, we prove that entrywise application of the block code MacWilliams Identity for the matrix HΛ t H −1 will result in a matrix that up to reordering of the entries coincides with the adjacency matrix of the dual code. Secondly, for codes where the dual does not have Forney indices bigger than one we will show that the reordering of the entries comes from a state space isomorphism. As a consequence, the resulting matrix is indeed a representative of the generalized adjacency matrix of the dual code. This is exactly the contents of our MacWilliams Identity Theorem.
We end the introduction with recalling the basic notions of convolutional codes. Throughout this paper let F = F q be a finite field with q = p s elements where p is prime and s ∈ N. (1.1) A k-dimensional convolutional code of length n is a submodule C of F[z] n of the form In other words, G is noncatastrophic and delay-free. We call G an encoder and the number δ := max{deg γ | γ is a k-minor of G} is said to be the degree of the code C. A code having these parameters is called an (n, k, δ) code. A basic matrix G ∈ F[z] k×n with rows g 1 , . . . , For characterizations of minimality see, e. g., [4,Main Thm.] or [16,Thm. A.2]. It is well-known [4, p. 495] that each convolutional code C admits a minimal encoder G. The row degrees deg g i of a minimal encoder G are uniquely determined up to ordering and are called the Forney indices of the code or of the encoder. It follows that a convolutional code has a constant encoder matrix if and only if the degree is zero. In that case the code can be regarded as a block code.
The weight of convolutional codewords is defined straightforwardly. We simply extend the ordinary Hamming weight wt(w 1 , . . . , w n ) := #{i | w i = 0} defined on F n to polynomial vectors in the following way.
Finally we fix the following notions. For δ > 0 we will denote by e 1 , . . . , e δ the unit vectors in F δ . For any matrix M ∈ F a×b we denote by im M := {uM | u ∈ F a } and ker M := {u ∈ F a | uM = 0} the image and kernel, respectively, of the canonical linear mapping u → uM associated with M . Moreover, for any subset S ⊆ F ℓ we denote by S the F-linear subspace generated by S. If S = {a 1 , . . . , a t } is finite we simply write a 1 , . . . , a t for S . We will also use the notation a, U := a + U for any a ∈ F ℓ and any linear subspace U ⊆ F ℓ .

Preliminaries
The controller canonical form of an encoder is a well-known means of describing convolutional codes. Since our paper is completely based on this description we will first present the definition of the controller canonical form and thereafter discuss some of the basic properties as needed later on. It also allows us to conveniently introduce the two block codes associated with a convolutional code that are crucial for our investigation.
k×n be a basic and minimal matrix with Forney indices δ 1 , . . . , δ r > 0 = δ r+1 = . . . = δ k and degree δ := k i=1 δ i . Let G have the rows g i = δ i ν=0 g i,ν z ν , i = 1, . . . , k, where g i,ν ∈ F n . For i = 1, . . . , r define the matrices Then the controller canonical form of G is defined as the matrix quadruple (A, As is made precise next the controller canonical form describes the encoding process of the matrix G in form of a state space system.
As a consequence, one has for From now on we will assume our data to be as follows.
The two index sets will be helpful in the sequel. One easily derives the following properties.
Remark 2.4 One has AB t = 0 and BB t = Ir 0 0 0 . Furthermore, im B = e i | i ∈ I and ker B = im (0 (k−r)×r , I k−r ) ⊆ F k . Finally, As a consequence, The following two block codes will play a crucial role throughout the paper.
Definition 2.5 For C as above we define C const := C ∩F n to be the block code consisting of the constant codewords in C. Moreover, let C C := im C D ⊆ F n and define r ∈ {0, . . . , n−k} such that dim C C = k + r.
The following properties of these codes are easily seen from the controller canonical form.
Remark 2.6 (1) Suppose the encoder matrix G is as in Definition 2.1. Then C C = im C D = g i,ν | i = 1, . . . , k, ν = 0, . . . , δ i . Recalling that two different encoders of C differ only by a left unimodular transformation it follows immediately that the block code C C does not depend on the choice of the encoder G but rather is an invariant of the code C. Since rank D = k it is clear that the dimension of C C is indeed at least k.
(2) One has dim C const = k − r and precisely, with the notation from (1), This also shows C const ⊆ C C . Furthermore we have im D = im B t D ⊕ C const .
In accordance with block code theory the dual of a convolutional code is defined with respect to the canonical bilinear form (a 1 , . . . , a n ), (b 1 , . . . , b n ) −→ n j=1 a j b j .
With this notation the dual code is explicitly defined as In the sequel we will also let β denote the canonical bilinear form on F ℓ for any ℓ ∈ N. In that case we will use the notation U ⊥ := {v ∈ F ℓ | β(v, u) = 0 for all u ∈ U } ⊆ F ℓ for the orthogonal of a subspace U ⊆ F ℓ . The different notation C versus U ⊥ for the dual of a convolutional code C versus a block code U is simply to avoid cumbersome notation later on. It is well known [17,Thm. 7.1] that if C is an (n, k, δ) code, then C is an (n, n − k, δ) code. (2.4) The two block codes from Definition 2.5 and the corresponding objects C C and C const for the dual code C behave as follows under duality.
Proposition 2.7 One has (C C ) ⊥ = C const . As a consequence, C has exactly n − k − r zero Forney indices and r nonzero Forney indices. Moreover, dim C C = n − k + r.
Proof: Using the notation and statement of Remark 2.6(1) we obtain where the second equivalence uses the fact that c is a constant vector. The consequences are clear from the definition of r and r. Using Equation (2.2) we obtain C const = im 1 1 0 1 0 while C C = F 5 2 . As a consequence, r = 3. It can easily be checked that the dual code C is generated by the basic and Moreover, This is indeed in compliance with Proposition 2.7 since (C C ) ⊥ = C const and (C Let us now return to the general case. Block code theory allows us to apply the MacWilliams transformation to the block codes in Proposition 2.7. Before doing so it will be useful to define the weight enumerator for arbitrary affine sets in F n as it will be needed in the following sections. Recall the Hamming weight wt(a) for a ∈ F n . Definition 2.9 Let C[W ] ≤n denote the vector space of polynomials over C of degree at most n. For any affine subspace S ⊆ F n we define the weight enumerator of S to be the polynomial we(S) := n j=0 α j W j ∈ C[W ] ≤n , where α j := #{a ∈ S | wt(a) = j}. We also put we(∅) = 0.
Recall that the classical MacWilliams Identity for block codes states that for k-dimensional codes C ⊆ F n = F n q one has we(C ⊥ ) = q −k H we(C) , (2.5) where H is the MacWilliams transformation Observe that the mapping H is C-linear and satisfies H 2 (f ) = q n f . It should be kept in mind that H depends on the parameters n and q. Since throughout this paper these parameters will be fixed we do not indicate them explicitly.
Let us now return to convolutional codes. Using (2.5) and Proposition 2.7 one immediately obtains Corollary 2.10 q k+r we( C const ) = H we(C C ) .

The Adjacency Matrix of a Code
The (weight) adjacency matrix as defined next has been introduced in [17] and studied in detail in [5]. The aim of this section is to survey the structure and redundancies of the adjacency matrix for a given convolutional code. Let the data be as in (1.1) and General Assumption 2.3. Recall from Remark 2.2 that the controller canonical form leads to a state space description of the encoding process where the input is given by the coefficients of the message stream while the output is the sequence of codeword coefficients. The following matrix collects for each possible pair of states (X, Y ) the information whether via a suitable input u a transition from X to Y is possible, i. e., whether Y = XA + uB for some u, and if so, collects the weights of all associated outputs v = XC + uD.
The set of all connected state pairs is denoted by ∆ ⊆ F.
Observe that in the case δ = 0 the matrices A, B, C do not exist while D = G. As a consequence, Λ = λ 0,0 = we(C) is the ordinary weight enumerator of the block code Example 3.2 Let the data be as in Example 2.8. In order to explicitly display the adjacency matrices corresponding to G and G we need to fix an ordering on the state space F 3 2 . Let us choose the lexicographic ordering, that is, we will order the row and column indices according to (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1). (3.1) Then it is lengthy, but straightforward to see that For instance, in order to compute the entry in the 4th row and 2nd column put X := (0, 1, 1), Y := (0, 0, 1). Using the controller canonical form as given in Example 2.8 one has XA + uB = Y if and only if u ∈ {(0, 0), (0, 1)} and thus Likewise we obtain for the dual code Later in Theorem 5.8 we will see that these two adjacency matrices determine each other in form of a generalized MacWilliams identity.

Remark 3.3 The adjacency matrix contains very detailed information about the code.
Firstly, it is well-known that the classical path weight enumerator of a convolutional code [9, p. 154] can be computed from the adjacency matrix, for details see in [17], [5,Thm. 3.8], and [9,Sec. 3.10]. Secondly, at the end of Section 3 in [5] it has been outlined that the extended row distances [10] as well as the active burst distances [6] can be recovered from the adjacency matrix. As explained in [10], [6] these parameters are closely related to the error-correcting performance of the code.
It is clear from Definition 3.1 that the adjacency matrix depends on the chosen encoder G. This dependence, however, can nicely be described. Since we will make intensive use of the notation later on we introduce the following.
By definition, the matrix P(P ) corresponds to the permutation on the set F δ induced by the isomorphism P . Notice that P is an isomorphism of groups and basically is the canonical faithful permutation representation of the group GL δ (F). Obviously, we have for any Λ ∈ C[W ] q δ ×q δ and any P := P(P ) ∈ Π the identity Now we can collect the following facts about the adjacency matrix.
Remark 3.5 (a) Using the obvious fact wt(αv) = wt(v) for any α ∈ F * and v ∈ F n one immediately has λ X,Y = λ αX,αY for all α ∈ F * . Hence Λ(G) is invariant under conjugation with permutation matrices that are induced by scalar multiplication on F δ , i. e., under conjugation with matrices P(P ) where P = αI for some α ∈ F * .
Hence the equivalence class of Λ(G) modulo conjugation by Π, where G is any minimal encoder, forms an invariant of the code. It is called the generalized adjacency matrix of C. Let us now return to Definition 3.1. Notice that (X, Y ) ∈ F is connected if and only if there exists some u ∈ F k such that (X, Y ) = (X, XA + uB). Using rank B = r we obtain Later on we will also need the dual of ∆ in F. With the help of Remark 2.4 it can easily be calculated and is given as follows.
In the next lemma will show that the nontrivial entries λ X,Y of the adjacency matrix can be described as weight enumerators of certain cosets of the block code C const . More precisely, we will relate them to the F-vector space homomorphism (3.3) Recall the notation a, U as introduced at the end of Section 1.
Right-multiplying the defining equation of this set with B t we get upon use of Remark 2.4 that Y B t = uBB t , which says that the first r entries of u are completely determined by Y . This shows . From im (0, I k−r ) = ker B, see Remark 2.4, we conclude that these two affine subspaces coincide. Hence, using Remark 2.6(2), we obtain This shows the first part of the lemma. If ϕ(X, Y ) ∈ C const , we immediately conclude where due to ϕ(X, Y ) / ∈ C const this union is disjoint. From this the last assertion can be deduced. 2 The lemma shows that the mapping ϕ and the block code C const along with the knowledge of ∆ fully determine Λ(G). Moreover, to find out how many state pairs (X, Y ) ∈ ∆ are mapped to C const , we will slightly modify the mapping ϕ.
where r is as in Definition 2.5.
Proof: The well-definedness of Φ simply follows from im ϕ ⊆ C C . As for the surjectivity notice that any row of C D that is not in C const is a row of the matrix C BB t D , see also Remark 2.6(2). Moreover, by Remark 2.4 we have im where the latter follows from the definition of the mapping ϕ along with Proposition 3.6. All this implies the surjectivity of Φ. Now part (a) is trivial. The surjectivity together Let us illustrate the results so far by the previous example.
Example 3.10 Consider again the data from Example 2.8 and 3.2. We can observe the following properties of the two adjacency matrices.
(1) The matrix Λ(G) has exactly 2 4 = 16 nonzero entries, while Λ( G) has exactly 2 6 = 64 nonzero entries. This is in compliance with Proposition 3.6 applied to C as well as C.
(2) Each nonzero entry of Λ(G) is the sum of two monomials, while each entry of Λ( G) is a monomial. This also follows from the first part of Lemma 3.8 since #C const = 2 while C const = {0}.
(3) There are 4 entries in Λ( G) that are equal to 1. This also follows from application of Lemma 3.9 and Lemma 3.8 to the dual code: we obtain 2 δ−r = 4 times the case λ X,Y = we( C const ) = 1 while the second case appearing in Lemma 3.8, being the difference of the weight enumerators of two block codes, never contains the monomial 1 = W 0 . Along the same line of arguments one can also explain that λ 0,0 is the only entry of Λ(G) containing the monomial 1 = W 0 .
As a consequence of Lemma 3.9 one has We are now prepared to clarify some more redundancies in the adjacency matrix of C.
is obvious from the first direct sum in (a) and the definition of ∆. As for (c) notice that by linearity and Lemma 3.9(a) ϕ(X, Y ) − ϕ(X + X ′ , Y + Y ′ ) ∈ C const . Hence ϕ(X, Y ) + C const = ϕ(X + X ′ , Y + Y ′ ) + C const and the result follows from Lemma 3.8. 2 Concerning Proposition 3.11(c) it is worth mentioning that the converse statement [λ X,Y = λX ,Ỹ =⇒ (X, Y ) − (X,Ỹ ) ∈ ker Φ] is in general not true as different affine sets may well have the same weight enumerator. Moreover, notice that the results above are obviously true for any direct complement of ∆ in F. Our particular choice of ∆ − will play an important role due to the following corollary. Corollary 3.12 One has ϕ| ∆ − = 0 and C C = (X,Y )∈∆ * ϕ(X, Y ) + C const ) with the union being disjoint.
Proof: The first part follows directly from the definition of all objects involved. The inclusion "⊇" of the second statement is obvious. For the other inclusion let XC + uD ∈ C C for some (X, u) ∈ F δ+k . Using that im D = im B t D + C const , see Remark 2.6(2), this yields XC + uD = XC + Y B t D + a for some Y ∈ F δ and a ∈ C const . Hence XC + uD ∈ ϕ(X, Y ) + C const where (X, Y ) ∈ F. Now ϕ| ∆ − = 0 and Lemma 3.9(a) imply that without loss of generality (X, Y ) ∈ ∆ * . The disjointness of the union follows from ∆ * ∩ ker Φ = {0} with the same lemma. 2 We will conclude this chapter by computing the sum over all entries of the adjacency matrix of a convolutional code in order to demonstrate how the terminology developed above facilitates this task. The result will be needed later on for proving Theorem 4.7.
Proposition 3.13 The entries of the adjacency matrix satisfy Proof: Using Lemma 3.8 and Corollary 3.12 we obtain Next notice that (X,Y )∈F λ X,Y = (X,Y )∈∆ λ X,Y as any disconnected state pair (X, Y ) satisfies λ X,Y = 0. Hence with Proposition 3.11(c) and Lemma 3.9(b) we get It is straightforward to verify the second result of this proposition for Example 2.8/3.2.

The MacWilliams Matrices
Recall the notation from (1.1) and fix some δ ∈ N. In this section we will define a set of complex matrices that are essential for our transformation formula as discussed in the next section, and we will collect some of their properties. To define the matrices we will use complex-valued characters on F δ , i. e., group homomorphisms (F δ , +) −→ (C * , ·). It is a well known fact [11,Thm. 5.5], that, using a fixed primitive p-th root of unity ζ ∈ C, the character group on F δ is given as {ζ τ (β(X, · )) | X ∈ F δ }, where τ : F −→ F p , a −→ s−1 i=0 a p i is the usual trace form and β is the canonical bilinear form on F δ . It will be convenient to define θ X := ζ τ (β(X, · )) : F δ −→ C * for all X ∈ F δ . (4.1) For easier reference we list the following properties.
Definition 4.2 Let ζ ∈ C * be a fixed primitive p-th root of unity. For P ∈ GL δ (F) we define the P -MacWilliams matrix as For simplicity we also put H := H(I). For δ = 0 we simply have H = 1.

Remark 4.3
Notice that the MacWilliams matrices depend on δ. Since this parameter will be fixed throughout our paper (except for the examples and Remark 4.6) we will not explicitly denote this dependence. Moreover, the matrices depend on the choice of the primitive root ζ. This dependence, however, can easily be described. Suppose ζ 1 and ζ 2 are two primitive p-th roots of unity and let H 1 and H 2 be the corresponding I-MacWilliams matrices. Then ζ d 1 = ζ 2 for some 0 < d < p and, using the F p -linearity of τ , it is easy to check that H 2 = P(dI)H 1 = H 1 P(d −1 I). Making use of Remark 3.5(a) this results in Since all later expressions will be of either of these forms, our results later on do not depend on the choice of ζ.
Obviously, the matrix H is symmetric. Moreover, all MacWilliams matrices are invertible since the q δ different characters are linearly independent in the vector space of C-valued functions on F δ . However, the inverse of these matrices can even easily be calculated. Recall the matrices P(P ) from Definition 3.4.

In particular the inverse of a MacWilliams matrix is a MacWilliams matrix again.
Proof: For the computation of H 2 fix any pair (X, Y ) ∈ F. Then, upon using the rules in Remark 4.1(b) and (c), The rest of the lemma can be checked in the same way using again Remark 4.1(c). 2 Example 4.5 Let p = q = 2 and δ = 3. Then ζ = −1 and with respect to the lexicographic ordering (3.1) on F 3 2 we obtain Remark 4.6 It should be mentioned that the MacWilliams matrices as presented here appear already in classical block code theory in the context of complete weight enumerators. Given a block code C ⊆ F n the complete weight enumerator is defined as Obviously, we obtain the ordinary weight enumerator we(C) from cwe(C) by putting X 0 = 1 and X a = W for all a ∈ F * . Let now δ = 1 and H ∈ C q×q be the corresponding MacWilliams matrix. Then H is the standard matrix interpretation of the Extending h to a C-algebra-homomorphism on C[X a | a ∈ F] it is well-known [14, Ch. 5.6, Thm. 10] that the complete weight enumerators of a kdimensional block code C ⊆ F n q and its dual satisfy the MacWilliams identity cwe(C ⊥ ) = q −k+ n 2 h cwe(C) . At this point it is not clear to us why the MacWilliams matrix appears in the seemingly unrelated contexts of complete weight enumerators for block codes and adjacency matrices for convolutional codes.
In the next section we will investigate a conjecture concerning a MacWilliams Identity Theorem for the adjacency matrices of convolutional codes and their duals. It states that for the data as in General Assumption 2.3 and for any P ∈ GL δ (F) the matrix q −k H H(P )Λ(G) t H(P ) −1 is a representative of the generalized adjacency matrix of C (in the sense of Remark 3.5(b)), see Conjecture 5.2. Using Lemma 4.4 and the fact H t = H one easily observes that HΛ(G)H = P(−I) HΛ(G) t H −1 t . Therefore the matrix HΛ(G)H will be particularly helpful and will be studied first. Let, as usual, the data be as in General Assumption 2.3 and Definition 3.1 and remember r from Proposition 2.7. Put ℓ X,Y := HΛ(G)H X,Y for (X, Y ) ∈ F. The entries ℓ X,Y can be described explicitly. In the sequel we will use for any pair (X, Y ) ∈ F the short notation (X, Y ) ⊥ := (X, Y ) ⊥ to denote the orthogonal space in F. The following result will be crucial for the MacWilliams Identity Conjecture as studied in the next section.
The last statement can be regarded as a counterpart to Proposition 3.11(c). In fact, both these invariance properties will be needed to derive a correspondence between the matrix HΛ(G)H and the adjacency matrix of the dual code in Section 5.
3) Let (X, Y ) ∈ ∆ ⊥ , which implies ∆ ⊆ (X, Y ) ⊥ and therefore (F\(X, Y ) ⊥ ) ∩ ∆ = ∅. Using Equation (4.3) together with the fact that λ Z 1 ,Z 2 = 0 for (Z 1 , Z 2 ) ∈ ∆ one gets where the last identity follows from Proposition 3.13. 4) Finally, for the last case let (X, Y ) ∈ (ker Φ) ⊥ \∆ ⊥ . Thus, ker Φ ⊆ (X, Y ) ⊥ , but ∆ (X, Y ) ⊥ . Again, using Equation (4.3) together with Proposition 3.13, we obtain 5) It remains to show ℓ X+U,Y +V = ℓ X,Y for any (U, V ) ∈ ∆ ⊥ . Since ∆ ⊥ ⊆ (ker Φ) ⊥ the statement is obvious in the first two cases of ℓ X,Y . For the remaining case notice that in the expression for ℓ X,Y we have for any (U, V ) ∈ ∆ ⊥ . This completes the proof. 2 At this point it is possible to derive a formula for the MacWilliams transformation H as defined in (2.6) applied to the entries ℓ X,Y . It will play a central role in the next section. Recall from (2.3) the notation C for the dual code of C. Notice from (4.2) that the polynomials ℓ X,Y are in C[W ] ≤n so that indeed the mapping H can be applied.
Proof: Use the form of ℓ X,Y as given in Theorem 4.7. The first case is immediate as H(0) = 0. The second case is exactly Corollary 2.10. The third case requires more work. Thus, let (X, Y ) ∈ (ker Φ) ⊥ \ ∆ ⊥ , hence ker Φ ⊆ (X, Y ) ⊥ , but ∆ (X, Y ) ⊥ . As a consequence, (X, Y ) ⊥ ∩ ∆ is a hyperplane of ∆ and ker Φ is contained in (X, Y ) ⊥ ∩ ∆. Using the direct complement ∆ * of ker Φ in ∆ as introduced in Proposition 3.11 we obtain (X, Y ) ⊥ ∩ ∆ = (X, Y ) ⊥ ∩ ∆ * ⊕ ker Φ and (X, Y ) ⊥ ∩ ∆ * is a hyperplane in ∆ * . With the help of Proposition 3.11(c) and Lemma 3.9(b) we get By Lemma 3.8 λ Z 1 ,Z 2 = we ϕ(Z 1 , Z 2 ) + C const and these cosets are pairwise disjoint for (Z 1 , Z 2 ) ∈ (X, Y ) ⊥ ∩ ∆ * , see Corollary 3.12. Therefore we obtain We will show next that H(X, Y ) ⊥ = C const , c(X, Y ) for some element c(X, Y ). In order to do so we need to compute the dimension of H(X, Y ). Since ker This implies dim H(X, Y ) ⊥ = n − k − r + 1 = dim C const + 1. Furthermore, H(X, Y ) ⊆ im ϕ + C const = C C and along with Proposition 2.7 this yields C const ⊆ H(X, Y ) ⊥ . All this shows that there exists some c(X, Y ) ∈ H(X, Y ) ⊥ \ C const such that where the last identity is again due to (2.5) and Corollary 2.10. This proves the desired result. 2 The last proposition together with Lemma 3.8 reveals an immediate resemblance of the entries q −k H(ℓ X,Y ) to that of any given adjacency matrix of the dual code of C. Indeed, firstly notice that both matrices have the same number of zero entries since #(ker Φ) ⊥ = q δ+ r is exactly the number of connected state pairs of the dual code. Moreover, Proposition 4.8 tells us that q −k H(ℓ X,Y ) has #∆ ⊥ = q δ−r entries equal to we( C const ). Applying Lemmas 3.8 and 3.9 to the dual code C we see that the adjacency matrix of the dual code has the same number of entries equal to we( C const ). The remaining entries also have an analogous form. All this indicates that there might be a strong relation between q −k H(ℓ X,Y ) and the adjacency matrix of the dual code. This will be formulated in a precise conjecture in the next section and proven for a specific class of codes. The difficulty for proving this will be, among other things, that we need a concrete description of the mapping (ker Φ) ⊥ \ ∆ ⊥ −→ F, (X, Y ) → c(X, Y ) as used in the last part of Proposition 4.8.

A MacWilliams Identity for Convolutional Codes
In this section we will formulate the MacWilliams identity and prove it for a particular class of codes. Let again the data be as in (1.1) and General Assumption 2.3. Denote the associated adjacency matrix Λ(G) simply by Λ. Furthermore, let C be the dual code. We fix the following notation.
General Assumption 5.1 Let C have encoder matrix G ∈ F[z] (n−k)×n and let the corresponding controller canonical form be denoted by ( A, B, C, D). Moreover let the associated adjacency matrix be written as Λ =: λ X,Y and let ∆ be the space of connected state pairs for C. Finally, we define the mappings ϕ and Φ for the code C analogously to (3.3) and Lemma 3.9 and, the spaces ∆ − and ∆ * analogously to Proposition 3.11. Recall from by Proposition 2.7 that C has r nonzero Forney indices.
We know from (2.4) that C and C both have degree δ and thus the adjacency matrices Λ and Λ are both in C[W ] q δ ×q δ . As a consequence we have all results of Section 3 literally available in a -version, and we will make frequent use of them.
Notice that duality implies G G t = 0. From Remark 2.2 we know that Conjecture 5.2 The matrix q −k H HΛ t H −1 , where H is applied entrywise to the given matrix, is a representative of the generalized adjacency matrix of C. In other words, there exists some P ∈ GL δ (F) such that Recall from Remark 3.5(b) that the adjacency matrices for two different minimal encoders of C differ by conjugation with a suitable matrix P(P ) ∈ Π. This explains the presence of the matrix P ∈ GL δ (F) above. Of course, P depends on the chosen encoders G and G.
It is worth mentioning that in the case δ = 0 Identity (5.2) immediately leads to the MacWilliams identity for block codes as given in (2.5). Notice also that, due to Lemma 4.4 and Equation (3.2), the conjecture implies the same statement if we replace H by an arbitrary Q-MacWilliams matrix H(Q).
The conjecture is backed up by many numerical examples. A proof, however, is still open for the general case. As a first step a somewhat weaker result will be proven in Theorem 5.5. Thereafter we will fully prove the conjecture for codes where δ = r or δ = r. In that case we will even be able to precisely tell which transformation matrix P ∈ GL δ (F), depending on G and G, to choose for (5.2) to be true. We need the following lemma. It still applies to the general situation.
Theorem 5.4 Let M ∈ F 2δ×2δ be as in Lemma 5.3. Then Moreover, due to (X, Y ) ∈ ∆ * \{0} we have ϕ(X, Y ) ∈ C const . Finally applying (5.3) to All this shows that we may choose c (X, Y )M in Proposition 4.8 as ϕ(X, Y ). Now that proposition yields and this coincides with λ X,Y due to Lemma 3.8. 2 For the sequel let G be any direct complement of (ker Φ) ⊥ in F. Due to Lemma 5.3(e) we have the following decompositions of F.
where, due to identical dimensions, there exist isomorphisms in each column. For f 0 we choose the isomorphism induced by the matrix M from Lemma 5.3, and thus M = im M as before. This picture leads to the following result.
As a consequence, In particular, the entries of the matrices Λ and q −k H HΛ t H −1 coincide up to reordering.
3) For the remaining case we have (X, Y ) ∈ ∆\ ker Φ. Writing (X, Y ) = (X 1 , Y 1 )+(X 2 , Y 2 ) where (X 1 , Y 1 ) ∈ ∆ * and (X 2 , Y 2 ) ∈ ker Φ, Proposition 3.11(c) yields λ X,Y = λ X 1 ,Y 1 while It needs to be stressed that the theorem does not prove Conjecture 5.2 since we did not show that f −1 (−Y, X) = (XQ, Y Q) for some suitable Q ∈ GL δ (F) and all (X, Y ) ∈ F. The difficulty in proving Conjecture 5.2 consists precisely in finding isomorphisms f 0 , f 1 , f 2 for Diagram (5.4) such that f −1 (−Y, X) has such a form. This will be accomplished next for the class of convolutional codes for which either r or r is equal to δ.
We begin with the case where r = δ. Notice that this is equivalent to saying that all nonzero Forney indices of C have value one. Therefore, in this case where the last part follows from minimality of the encoder G. Furthermore, im D 2 = C const . We will need the following technical lemma.
Lemma 5.6 Let r = δ. Then the controller canonical forms satisfy Proof: (1) Since r = δ we have B t = (I δ , 0) and thus B t D consists of the first δ rows of D. As a consequence, B t D has full row rank δ. Suppose now that rank B t DC t < δ.
Since DD t = 0 this implies rank B t D(C t , D t ) < δ. Hence there exists a nonzero vector a ∈ F δ such that a B t D(C t , D t ) = 0. In other words, a B t D ∈ (C C ) ⊥ = C const , where the last identity follow from Proposition 2.7. Now the full row rank of B t D shows that im B t D ∩ C const = {0}, a contradiction to Remark 2.6(2) applied to the code C. Hence rank B t DC t = δ.
(2) By duality we have GG t = 0. From Remark 2.2 we know that the controller canonical forms determine the corresponding encoders via where due to nilpotency the sums are finite. Since r = δ all Forney indices of C are at most one and therefore A = 0. Hence G = z B C + D. Now we compute Hence the coefficients of z l , l ≥ 1, are zero. Left multiplying the coefficient of z by B t , right multiplying it by B, and using B t B = I this implies the identity Furthermore, if we multiply the coefficient of z l by B t from the left and by BA l−1 from the right we obtain where the last identity is due to Remark 2.4. Addition of these equations yields where the last identity follows from the nilpotency of A. Now we conclude with Remark 2.4 and the aid of (5.7) which is what we wanted. 2 Now we can present an isomorphism f 1 for Diagram (5.4).
Proof: (a) Using Lemma 3.7 it suffices to show that ( CC t ) ij = 0 for all 1 ≤ i ≤ δ and j ∈ J . From (5.6) we see that all rows in C are leading coefficient rows in G. By definition of the controller canonical form the jth rows of C, where j ∈ J , are leading coefficient rows of the encoder G. Now GG t = 0 implies the desired result. As a consequence we also have rank M 1 ≤ δ − r.
(b) From Lemma 5.6 we know that B t DC t ∈ GL δ (F). Let now (X, Y ) ∈ ker Φ ∩ ker M 1 . Then X CC t = 0 and, due to Lemma 5.3(b) we also have (X, Y )M = 0. As a consequence, X CC t + Y B t DC t = Y B t DC t = 0 and from the above we conclude Y = 0. Now (X, 0) ∈ ker Φ yields ϕ(X, 0) = X C ∈ C const . Using the full row rank of the rightmost matrix in (5.6) we conclude X = 0. (c) follows from (a) and (b) since dim ker Φ = δ − r. 2 Now we are able to prove our main result. The crucial step will be a suitable choice for the space ∆ * . Recall that, so far, ∆ * was just any direct complement of ker Φ in ∆. As we will see below, ker M 1 is such a direct complement.
Theorem 5.8 Let r = δ, that is, each Forney index of the code C is at most 1. Then Q := − B t DC t ∈ GL δ (F) and As a consequence, where the MacWilliams transformation H has to be applied entrywise.
Proof: The invertibility of Q = B t DC t has been shown in Lemma 5.6(1). Choose the matrices M and M 1 as in Lemmas 5.3 and 5.7. By Lemma 5.6(2) we have Notice that due to r = δ we have F = ∆. In particular, the last column of Diagram 5.4 is trivial. Lemma 5.7 shows that ∆ * := ker M 1 is a direct complement of ker Φ in F. and, using the lexicographic ordering (3.1), the permutation matrix is given by Using this as well as the adjacency matrices given in Example 3.2 and the MacWilliams matrix H in Example 4.5 one can check straightforwardly Identity (5.8).
We can easily transfer our result to convolutional codes with δ = r.
Theorem 5.10 Let δ = r, that is, each Forney index of the code C is at most 1. Then P := − CD t B ∈ GL δ (F) and for all (X, Y ) ∈ F we have λ X,Y = q −k H (HΛ t H −1 ) XP,Y P . In other words, Λ = q −k H P(P )HΛ t H −1 P(P ) −1 .
Proof: Notice that we can apply Theorem 5.8 to the code C. Hence Q := −B t D C t is regular and, since dim C = n−k, we obtain Λ = q −n+k H(P(Q)H Λ t H −1 P(Q) −1 ). Applying Incorporating the permutation matrix into the MacWilliams matrix, see Lemma 4.4, we can state Theorems 5.8 and 5.10 in terms of P -MacWilliams matrices only.
Using the notion of the generalized adjacency matrix as defined in Remark 3.5(b) we obtain the following consequence, formulated independently of any chosen representation.
Theorem 5.12 Let r = δ or r = δ. Then the generalized adjacency matrix of C uniquely determines the generalized adjacency matrix of the dual code C. More precisely, let [Λ] and [ Λ] be the generalized adjacency matrices of C and C, respectively. Then, in a suggestive notation, [ Λ] = q −k H(H[Λ] t H −1 ).
We close this section with an example supporting Conjecture 5.2 that is not covered by the cases in Theorem 5.8 or Theorem 5.10.
Example 5.13 Let q = 3, thus F = F 3 , and G = 1+z 2 2+z 0 1 0 2 . Put C = im G. Then G is a minimal basic matrix and thus C is a (3, 2, 2) code. The dual code is given by C = im G where G = 2 + z 2 + 2z 2 2 + z . Notice that r = r = 1 = δ. Using the controller canonical forms one can straightforwardly compute the adjacency matrices Λ, Λ ∈ C[W ] 9×9 . Then, via a systematic search one finds that Identity (5.2) is satisfied if one chooses the regular matrix P = ( 1 1 1 2 ) ∈ GL 2 (F 3 ). In the same way one can establish plenty of examples.

Unit Constraint-Length Codes
In the last section we want to have a closer look at codes with degree δ = 1, also called unit constraint-length codes or unit memory codes. Notice that in this case r = r = δ = 1. The situation now becomes particularly simple since, firstly, GL δ (F) = F * and, secondly, the adjacency matrices Λ and Λ do not depend on the choice of the encoder matrices G and G. The latter is a consequence of Equation (3.2) along with Remark 3.5(a), (b). Notice also that in Diagram (5.4) the second and third column are trivial. Using once more Remark 3.5(a), we finally see that the statements of both Theorem 5.8 and Theorem 5.10 reduce to the nice short formula Λ = q −k H(HΛ t H −1 ). (6.1) In the paper [1] the so-called weight enumerator state diagram has been studied for codes with degree one. They are defined as the state diagram of the encoder where each directed edge is labeled by the weight enumerator of a certain affine code. A type of MacWilliams identity has been derived for these objects [1,Thm. 4]. It consists of a separate transformation formula for each of these labels. After some notational adjustment one can show that the weight enumerator state diagram is in essence identical to the adjacency matrix of the code. Furthermore, if stated in our notation, the MacWilliams identity in [1,Thm. 4] reads as λ X,Y =    q −k−1 H λ 0,0 + (q − 1)(λ 0,1 + Y ∈F λ 1,Y ) if (X, Y ) = (0, 0) q −k−1 H λ 0,0 + qλ X,Y − λ 0,1 − Y ∈F λ 1,Y else.

(6.2)
In the sequel we will briefly sketch that this result coincides with Identity (6.1). In order to do so use again ℓ X,Y as introduced in (4.2). Then (6.1) turns into λ X,Y = q −k H(ℓ −Y,X ) for all (X, Y ) ∈ F. Using (6.3) this yields the first case of (6.2). For the second case let (X, Y ) ∈ F \(0, 0). Since ∆ ⊥ = {0} and (ker Φ) ⊥ = F one observes that in Theorem 4.7 the third case has to be applied. Along with Proposition 3.13 and Remark 3.5(a) this yields Combining this with (6.3) leads to the second case of (6.2).

Conclusion
In this paper we studied the adjacency matrices for convolutional codes. We introduced a transformation consisting of conjugation with the MacWilliams matrix followed by entrywise application of the MacWilliams Identity for block codes. We proved that the resulting matrix coincides up to reordering of the entries with the adjacency matrix of the dual code, and we presented the reordering mapping explicitly. This result can be regarded as a weak MacWilliams Identity for convolutional codes. However, we strongly believe that the reordering of the entries can even be expressed in terms of an isomorphism on the state space, and indeed, we proved this statement for a particular class of convolutional codes. The general case has to remain open for future research.