# Presentation: 257757

**Analysis and Applications **

- Ljupco Kocarev
*University of California, San Diego*

## Summary of the presentation

-  Nonlinear Dynamics of the iterative coding systems
-  Nonlinear Codes with Latin Squares (Quasi-groups)
-  Conclusions

**When:** since 2002
**Who:** Alex Vardy (UCSD)
-           Gian Mario Maggio (ST, Swiss)
-           Zarko Tasev  (Kyocera, USA)
-           Frederic Lehmann (INT, Paris, France)
-           Pater Popovski (Tech University, Denmark)
-           Bartolo Scanavino (Poli Torino, Italy)

**Why: **
- To understand finite-length iterative decoding algorithms using tools from nonlinear systems and chaos theory; and
- To exploit chaos theory for enhancing existing iterative coding techniques and invent new classes of error-correcting codes.

**Sponsors:** ARO (MURI), STMicroelectronics, University of California (DIMI)

## Understanding finite-length iterative coding systems  

-  Codes on graphs as spin models (1989)
-  Finite length scaling for iterative coding systems (2004)
-  Renormalization group approach for iterative coding systems (2003)
-  Scale-free networks and error-correction code (2004)
-  Nonlinear dynamics of iterative coding systems (2000)

*As of today asymptotic behavior (as the block-length tends to infinity) *
*of iterative coding systems is reasonably well understood  *

- Tom Richardson: The geometry of turbo decoding dynamics (2000)

## Kalman’s example

- R. E. Kalman, 1956
- “Nonlinear aspects of sampled-data control systems”

*x*n+1

*x*n

- 1/3

- 2/3

- 1

- 1/3

- 1

- 0

- 0

- 1

- S

- 1

- 0

- S

- Markov process with transition probabilities:

- Logistic map:     *x**n+1** = a x**n** ( 1 – x**n** )      a = 3.839*

## Turbo codes

- n=1024

- Classical turbo codes: C. Berrou, A Glavieux, and P. Thitimajshima,
- “Near Shannon limit error-correcting  coding and decoding: Turbo-Codes,”
- Proc. IEEE International Communications Conference, pp. 1064-70,  1993

## Turbo-decoding algorithm 

- BCJR algorithm, 1974

- AWGN channel

*X**1*,* X**2*  - extrinsic information exchanged by the two SISO decoders

*c**0*, *c**1*, *c**2* - channel outputs corresponding to the input sequences

- The system depends smoothly on its *2n* variables *X**1*,* X**2* and *3n* parameters *c**0*, *c**1*, *c**2 *
-                                                                                                    (Richardson)

-  *E* represents  *a posteriori average entropy*

- Three types of plots: *E(l)* versus *l*, *E(l+1)* versus *E(l)*, and *E* versus SNR.

## Bifurcation diagram 

## Discrete-time Hopf bifurcation (part I)

- -6.7dB

- -6.5dB

- -5.9dB

- -6.3dB

- -6.1dB

- 0.75dB

- 0.8dB

- 0.85dB

## Discrete-time Hopf bifurcation (part II)

- -6.7dB

- -6.6dB

- -6.5dB

- -6.3dB

- -6.2dB

- -6.1dB

## Example: 2D map 

- Attracting fixed point
- Attracting invariant curve
- Chaotic attractor

*a *=   1.9, 2.1, 2.16, 2.27

## Tangent bifurcation (part I)

- -7.65dB

- -7.645dB

- -7.6dB

- 0.3dB

- 0.35dB

- 0.4dB

## Tangent bifurcation (part II)

- -7.65dB

- -7.65dB

- -7.64dB

- -7.64dB

## One-dimensional approximation

## One-dimensional approximation

## Lyapunov exponents 

## Transient chaos 

-  The unequivocal fixed point
-    becomes stable around –1.5dB.
-   Region 0.25dB to 1.25dB
-    (waterfall region): transient chaos
-  Average chaotic transient lifetime
-   for SNR=0.8dB is 378 iteration

## Transient chaos 

- For each SNR, we generate 1000 different noise realizations
- (1000 different parameters frames) and compute the number of
- decoding trajectories that approach the fixed point in less than a given number of iterations.

- At SNR of 0.6dB, there are 492 frames that converge to the unequivocal fixed point in 5 or less iterations, another 226 frames converge in 10 or less iterations, and so on, while 58 frames remain chaotic after 2000 iterations (which means that their trajectory either approaches a chaotic attractor or that the transient chaos lifetime is very large).

## Stability of the fixed point  

## LDPC codes

- Torus-breakdown route to chaos for
- the regular (216,3,6) LDPC code

- The values of SNR corresponding to the invariant sets, starting from the fixed point towards chaos, are:
-                        1.19 dB, 1.23 dB, 1.27 dB, 1.33 dB, and 1.44 dB

## Control of transient chaos 

- Average chaotic transient lifetime for SNR=0.8dB is 9 iterations.

## Control of transient chaos: results

## Control of transient chaos: results

## Conclusions 

- Iterative decoding algorithms can be viewed as high-dimensional dynamical systems parameterized by a large number of parameters. However, although the iterative-decoding algorithm is a high-dimensional dynamical system, it apparently has only a few active variables.
- The waterfall region for all iterative coding systems exhibits reach dynamical behavior: chaotic attractors, transient chaos, multiple attractors and fractal basin boundaries.
- Applications:

- We have proposed a simple adaptive technique to control transient  chaos in the turbo decoding algorithm. This results  in a ultra-fast convergence and a significant gain in terms of BER performance.
- We have proposed a novel stopping criterion for turbo codes based on the average entropy of an information block. This is shown to reduce the average number of iterations and to benefit from the use of the adaptive control technique.

## Open problems:  

- Study how the size of the basin of attraction changes with varying SNR.
- Find how the value of SNR for which the fixed point at origin becomes a stable point related to the threshold which gives the boundary of the error-free region.
- Study whether the chaotic behavior of the iterative coding systems comes from the presence of cycles in the graph.
- Investigate how the topological structure of unstable periodic orbits embedded into the chaotic set is related to the topological structure of the factor graph.
- Use ergodic theory for dynamical systems to study the properties related to a set of trajectories, not a single trajectory.
- Find models of low-dimensional dynamical systems averaged over ensembles and/or different noise realizations.

## Latin Squares (Quasigroups)

- A Latin square of order *N *is *N*x*N* array of numbers from *N*-symbol alphabet
- (say *0, 1, 2,  ... N-1*) in which each row and each column contains each symbol exactly once.
- Latin squares are also linked to algebraic objects known as quasigroups. A quasigroup is defined in terms of a set, Q, of distinct symbols and a binary operation (called multiplication) involving only the elements of Q.
- A quasigroup's multiplication table turns out to be a Latin square.

- D. Gligoroski, S. Markovski (since Sep 2004)

- Given a quasigroup (Q,*) five new operations, so called parastrophes or adjoint operations, can be derived from the operation *.
- We need only the following one defined by:
- (Q,\) is also a quasigroup.

## Quasigroup string transformations

- e-transformation

- d-transformation

- Let* Q*+ be the set of all nonempty words (i.e. finite strings) formed by the elements of *Q*.

## Nonlinear Codes with Latin Squares (Quasigroups)

-       (*Q*,*)         *Q* = {*0, 1, 2,  ... N-1*}
*M**1*, *M**2*, ..., *M**r*             information string; each *M**i* is an element of *Q*
*L**1*, *L**2*, ..., *L**m *               *m> r      *   Each *L**i*  is either *M**i*  or 0
*C**1*, *C**2*, ..., *C**m*              codeword

*k**1*, *k**2*, ..., *k**n*             leaders
- each *k**i* is an element of *Q*

- (Q,\) is the left parastrophe of the quasigroup (Q,*)

## Properties of the Code 

-  Nonlinear code
-  “Almost random” code
* **C**1*, *C**2*, *?*, *C**3*, ..., *C**m*                       *L**1*, *L**2*, *?*, *?*, ...., *? *
-     (synchronous and self - synchronized stream ciphers)

## Example

-       (*Q*,*)         *Q* = {*0, 1, 2,  ... 15*}    Quasigroup of order 16
-       Each *M**i* is a nibble (4-bit string)

- (72,288) code with rate 1⁄4              r = 18, m = 72

## Decoding the code 

- BSC

*D**i* is a nibble and  *D**(i)*  is a sub-block of 4 nibbles (16 bits)

- If the set *S**s* contains only one element we say the decoding is successful

- (72,288) code with rate 1⁄4              r = 18, m = 72

*B*max = 3

## Stability of the decoding algorithm 

- Theorem:   If the decoding is successful, then the message is recovered with probability 2*-N(1-R)*

- Conjecture:  If

- then the decoding procedure converges and the cardinality of* S*s is 1.

- The relative Gilbert-Varshamov (GV) distance

## Example

-    Reed – Muller code  (6,32)    rate 3/16   corrects  up to 7 errors
-  Total number of noisy code-words the codes can correct is 4.5 x 106

*N *= 32     *B**max* = 8        (*B*2 = 8)

- m1  m2 02 02 02 02 02 02        m3  02 02 02 02 02 02 02

*B**max* = 5          68852 ~ 4.7 107

- (6,32)    rate 3/16

## Conclusions (open problems)

- Theoretical framework
- AWGN channel, soft decoding
- Concatenated codes: Si is intersection of two sets Si(1) and Si(2)