http://wol.ra.phy.cam.ac.uk/mackay/gallager/TCC.html

TCC.p

- grammar and perl program for making matrices and pictures (ps) of trellis constrained codes

Source code is in ~mackay/bin/TCC.p.

Example:

A standard rate 1/3 Turbo code can be defined by connecting N=3K codeword bits to two trellises each of which corresponds to a rate 1/2 convolutional code. One way of representing these trellis constraints is by a matrix whose columns correspond to codeword bits and whose rows correspond to dangling connections in the trellises. Every row has weight at most one because each edge in the trellis can only be connected to one bit. Each column has weight one or two depending whether the codeword bit in question is a source bit or a parity bit. Here is the connectivity matrix for a tiny Turbo code with K=4 and N=12

 Connectivity matrix of rate 1/3 Turbo code
 
 source  parity  parity
  bits    bits    bits
 _______________________  
 1 . . .|. . . .|. . . .  ^
 . 1 . .|. . . .|. . . .  |
 . . 1 .|. . . .|. . . .  |
 ______1|_______|_______  First trellis
 . . . .|1 . . .|. . . .  |
 . . . .|. 1 . .|. . . .  |
 . . . .|. . 1 .|. . . .  |
 _______|______1|_______  V            
 . . 1 .|. . . .|. . . .   ^            
 . . . 1|. . . .|. . . .   |            
 . 1 . .|. . . .|. . . .   |            
 1______|_______|_______  Second trellis
 . . . .|. . . .|1 . . .   |            
 . . . .|. . . .|. 1 . .   |            
 . . . .|. . . .|. . 1 .   |            
 _______|_______|______1   V            
 
We define the BIT PROFILE of this code to be a summary of the weight per column. This profile can either be reported column by column thus:
 2 2 2 2 1 1 1 1 1 1 1 1
 
or using fractions of the total number of codeword bits
 2: 1/3
 1: 2/3
 

This matrix should not be confused with the parity check matrix of the code, which we could obtain by multiplying this matrix C on the left by a block diagonal matrix whose blocks are the parity check matrices of the constituent codes. We can work out the rate of the code by imagining this matrix multiplication.

Using the same representation we can show the connectivity matrix of a standard rate 1/2 Turbo code which is obtained by puncturing the above code. This corresponds to striking out parity bits. We will deliberately leave the definition of the trellis unchanged, so that now there are some rows in the connectivity matrix which have weight zero.

 Connectivity matrix of rate 1/2 Turbo code
 
 source  
  bits   
 _______________  
 1 . . .|. .|. .  ^
 . 1 . .|. .|. .  |
 . . 1 .|. .|. .  |
 ______1|___|___  First trellis
 . . . .|1 .|. .  |
 . . . .|. .|. .  |
 . . . .|. 1|. .  |
 _______|___|___  V            
 . . 1 .|. .|. .   ^            
 . . . 1|. .|. .   |            
 . 1 . .|. .|. .   |            
 1______|___|___  Second trellis
 . . . .|. .|1 .   |            
 . . . .|. .|. .   |            
 . . . .|. .|. 1   |            
 _______|___|___   V            
 
The profile of this Turbo code is
 2: 1/2
 1: 1/2
 
There are many other ways in which N bits could be connected to trellises, and we (Frey and MacKay) are investigating this space of connectivities to see if we can improve on Turbo codes. One idea was that it might be good to get rid of the weight 1 columns in the connectivity matrix, thus having a more regular connectivity. One way of doing this was to make a homogenous trellis constrained code by forcing the parity bits to be identical. This can be shown schematically as follows, though in order to make a code with a reasonable rate, we didn't make it quite this way; rather, we used constituent trellises with different rates from 1/2 and different puncturing schemes.
 Connectivity matrix of a homogenous TCC. 
 
 source  
  bits   
 ____________  
 1 . . .|. .|  ^
 . 1 . .|. .|  |
 . . 1 .|. .|  |
 ______1|___|  First trellis
 . . . .|1 .|  |
 . . . .|. .|  |
 . . . .|. 1|  |
 _______|___|  V            
 . . 1 .|. .   ^            
 . . . 1|. .   |            
 . 1 . .|. .   |            
 1______|___  Second trellis
 . . . .|1 .   |            
 . . . .|. .   |            
 . . . .|. 1   |            
 _______|___   V            
 
The profile of this Turbo code is
 2: 1
 
Another idea we are now exploring is to make the turbo code more irregular. For example, by identifying the first two source bits with each other, we obtain a lower rate code:
 Connectivity matrix of an irregular Turbo code
 
 source  
  bits   
 _____________  
 1 . .|. .|. .  ^
 1 . .|. .|. .  |
 . 1 .|. .|. .  |
 ____1|___|___  First trellis
 . . .|1 .|. .  |
 . . .|. .|. .  |
 . . .|. 1|. .  |
 _____|___|___  V            
 . 1 .|. .|. .   ^            
 . . 1|. .|. .   |            
 1 . .|. .|. .   |            
 1____|___|___  Second trellis
 . . .|. .|1 .   |            
 . . .|. .|. .   |            
 . . .|. .|. 1   |            
 _____|___|___   V            
 
The profile of this Turbo code is
 4: 1/7
 2: 2/7
 1: 4/7
 
We call the bits with high connectivity `privileged bits', because they are bits which get more likelihood information in the first iterations of sum-product decoding.

Another way to make an irregular turbo code with the same profile is shown below. This has the flavour of a `super-poisson' construction, in that one of the trellises is a privileged trellis containing more than the average number of connections to privileged bits (it has 3 connections to the one privileged bit); and the other trellis has fewer connections to privileged bits.

 Connectivity matrix of an irregular Turbo code
 
 source  
  bits   
 _____________  
 1 . .|. .|. .  ^
 1 . .|. .|. .  |
 . 1 .|. .|. .  |
 1____|___|___  First trellis
 . . .|1 .|. .  |
 . . .|. .|. .  |
 . . .|. 1|. .  |
 _____|___|___  V            
 . 1 .|. .|. .   ^            
 . . 1|. .|. .   |            
 . . 1|. .|. .   |            
 1____|___|___  Second trellis
 . . .|. .|1 .   |            
 . . .|. .|. .   |            
 . . .|. .|. 1   |            
 _____|___|___   V            
 
The profile of this Turbo code is, as before.
 4: 1/7
 2: 2/7
 1: 4/7
 
A brief specification of these connectivity matrices may be given as follows: each trellis is divided into c, eg, c=two, chunks, and then we list for each bit how many connections it makes to each chunk.

We call the following matrices the construction matrices. They contain more information than the profile because there is information about which trellises each highly connected bit is connected to.

# Construction matrix for rate 1/3 Turbo code

 1 1 1 1 0 0 0 0 0 0 0 0
 0 0 0 0 1 1 1 1 0 0 0 0
 1 1 1 1 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 1 1 1

 Construction matrix for rate 1/2 Turbo code

 1 1 1 1 0 0 0 0
 0 0 0 0 1 1 0 0
 1 1 1 1 0 0 0 0
 0 0 0 0 0 0 1 1

# Construction matrix for the slightly silly homogenous TCC

 1 1 1 1 0 0
 0 0 0 0 1 1
 1 1 1 1 0 0
 0 0 0 0 1 1

# Construction matrix for 1st irregular Turbo code

 2 1 1 0 0 0 0
 0 0 0 1 1 0 0
 2 1 1 0 0 0 0
 0 0 0 0 0 1 1

# Construction matrix for 2nd irregular Turbo code

 3 1 0 0 0 0 0
 0 0 0 1 1 0 0
 1 1 2 0 0 0 0
 0 0 0 0 0 1 1
Of the above four codes, all except the homogenous TCC are `fast-encodeable' in that they have a transparent `systematic' form; the source bits can be freely set then the parity bits can be deduced by consulting the trellises independently. It is possible that better codes would be obtained by looking at constructions which do not have this fast encodeable structure. (e.g. codes in which the construction matrix doesn't have those generous 1s dangling on the right hand side)
The program TCC.p is a program for reading construction matrices and spitting out connectivity matrices that satify those constructions. It also draws a picture of the bipartite graph.

The main things it does: invent random permutation matrices; figure out whether puncturing has occured and allow for it. It also computes the rate of the code.

The program has also to read in the trellis specifications. For the above codes the trellis specification is

# Number of trellises:
T=2
# Trellis 1:            here is the version without comments:
K=4 2 chunks
#                         T=2
# chunk a:                K=4 2 chunks     
 4  permute		   4  permute      
# chunk b:		   4               
 4 			  K=4 2 chunks     
# Trellis 2:		   4  permute      
K=4 2 chunks		   4               
# chunk a:
 4  permute
# chunk b:
 4
# another option is to say     4 puncture if you want it to show a gappy connectivity
Here K indicates the number of degrees of freedom (in bits) that this trellis, by itself, allows. If Nt codeword bits are linked to this trellis, then it invokes (Nt-Kt) constraints on the codewords.
If the word "permute" is there then the bits in that chunk are allocated at random to the corresponding codeword bits; otherwise the bits are doled out in order.


David MacKay <mackay@mrao.cam.ac.uk>
Last modified: Tue Jul 14 23:36:50 1998