Estimating computional complexity
The computational load that this implementation of the turbo-code algorithm is relatively modest, whether it's estimated in terms of the cycles per bit or the memory required to perform the tasks.

Cycle estimation. As shown in Listing 3 and Listing 4, the cycles consumed per bit for unpacking, interleaving and packing of interleaved data are four. In encoding of data as shown in Listing 2, we spend 2.5 cycles per bit. With this, the turbo encoder total cycle cost is 6.5 cycles per bit. Note that the overhead cycles are not included in this estimation. Assuming over head of one cycle per bit, we consume about 7.5 cycles per bit for performing turbo encoding. With this efficient implementation, we use 108 MIPS of Blackfin processor or approximately 18% of processor MIPS at bit-rate of 14.4 Mbps. Where as, we use 60% of processor MIPS with simple-encoding method. With 18% of MIPS consumed by turbo encoder, we have sufficient headroom of about 82% of processor MIPS to fit the other modules of femtocells base station.

Memory estimation. With the look-up-table method for turbo encoding, we need 256 bytes of data memory to store precomputed encoding information. With the efficient method, we need less data memory (by a factor of eight) for storing the interleaved data as we pack the bits to bytes. Both methods require data memory for storing interleaver addresses as it is costly to compute interleaver addresses on the fly.

Using the precomputed look-up table, we are able to perform turbo encoding using only 18% of processor MIPS; otherwise we consume about 60% of MIPS with simple methods. For this efficient method, the memory size of 256 bytes is used to store the look-up table and the overall memory used is less when compared to simple methods.

Hazarathaiah Malepati joined Analog Devices in 2003, where he is currently working on embedded algorithm software development for the Blackfin family of processors. From 2000 to 2003, he worked as a research engineer in HIRP (HFCL-IISc research program), Bangalore, India. He has a masters in industrial electronics from KREC, Surathkal.