**Non-commutative convolutional codes**

**Marion Candau**

**Roland Gautier**

**over the infinite dihedral group**

**Johannes Huisman**

marion.candau@univ-brest.fr

marioncandau.fr

**Thank you for your attention**

**Convolutional codes**

**Infinite dihedral group**

Electronically

Mathematically

**group law**

**polynomial ring**

G transfer matrix

u message

Encoding

SERIALIZER

transfer function

Encoding

Why

?

Encoding = convolution over

Convolution over

Product of two polynomials in

for a,b in

Non-commutative group

with X and Y non-commutative

Injectivity

Theorem

Let

. We define

Let

. Then N is a norm

in

.

P is not a right zero divisor

**0 1 2 3 4 5 6 7 8**

(-4,0) (-3,1) (-3,0) (-2,0) (-2,1) (-1,0) (-1,1) (0,0) (0,1) (1,0) (1,1) (2,0) (2,1) (3,0) (3,1)

**u**

**c**

1

X

Y

**u**

**c**

XY

YX

XYX

YXY

YXYX

XYXY

**Convolutional codes over the infinite dihedral group**

**redundancy**

**redundancy**

**Encoding**

shift register

Electronically

S

E

R

I

A

L

I

Z

E

R

**Multiplexing**

**Decoding**

**Properties**

**Conclusion**

convolution

convolution -1

convolution 0

convolution 1

convolution

u

**adapted Viterbi's algorithm**

**Two trellis which alternate in algorithm :**

**same complexity as the standard Viterbi's algorithm**

Same complexity of encoding and decoding as classic convolutional codes

For a given encoding circuit, two ways :

beginning with

or beginning with

two free distances

If we choose the beginning of the encoding then (with G transfer matrix)

If not :

Non-commutativity

Scenario : an attacker intercepts a piece of code word

He needs to perform two Viterbi's algorithm

Encoding and decoding are as simple as over

BUT :

Same maximum free distance as codes over

Complexity of attack is only x2 than over

**Perspectives**

Study another codes over non-commutative groups (work in progress)

Study how non-commutativity of group impacts properties of code (that's why I am here)

If

m

1

m

2

c

Convolution

Convolution

then

decoding problem

So convolution must be injective

is not a right zero divisor

experimental results

XYXYX

XYXYXY

YXYXY

YXYXYX

Examples

**Example**

Example

**Example with n=3**

YXYXYXY

XYXYXYX

1001000

begin with blue arrow

result : 001110011100000

= YXYXY + YXYX + YXY + 1 + X + XY

110

0 0 0 0 0

0 1 1 0 0

1 1 1 1 0

= 001110011100000

= YXYXY + YXYX + YXY

+ 1 + X + XY

= Y + YX + 1 + XY + YXYX

= (1+YXY)Y + 1 + (XYX + YXY)X

u = 1 + YXY

**one associated with**

red arrow

one associated with

blue arrow

red arrow

one associated with

blue arrow

**Example**

**000**

001

010

011

100

101

110

111

001

010

011

100

101

110

111

**000**

001

010

011

100

101

110

111

001

010

011

100

101

110

111

**000**

100

001

101

010

110

011

111

100

001

101

010

110

011

111

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

**000**

100

001

101

010

110

011

111

100

001

101

010

110

011

111

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

000

101

001

100

110

011

111

010

000

101

001

100

110

011

111

010

000

001

101

100

110

111

011

010

000

001

101

100

110

111

011

010

**adapted Viterbi's algorithm**

000

100

010

110

001

101

011

111

000

100

010

110

000

100

000

**or**

000

100

010

110

001

101

011

111

000

100

010

110

000

100

000

**according to the message's length**

with m memory, n number of outputs per bit, d free distance

f

000

100

010

110

001

101

011

111

000

100

010

110

000

100

000

or

000

100

010

110

001

101

011

111

000

100

010

110

000

100

000

Problem for him :

?

Complexity of attack : x 2

**eeee**

Transfer matrix to transfer function

Encoding :

u G

with :

and

Encoding :

u

and adapted serializer

with :

and

**1 0 0 1 0 0 0**

**1 0 1 1 1 0 1 0 0**

**0 0 1 1 1 0 0 1 1 1 0 0 0 0 0**

Because

Not injective :

Because

Injective :

c

c

c

C

C

c

C

c

c

c

**C**

**c**

0

0

1

1

...

...

**Classic convolutional codes :**

**Viterbi's Algorithm**

**Search for the code word closest to the received word**

Example

00

01

10

11

00

10

01

11

00

00

01

01

11

11

10

10

0

1

0

0

0

1

1

1

Algorithm

00

01

10

11

00

01

10

11

00

01

10

11

00

01

10

11

We have received 010111

01

01

11

1

0

2

1

1

2

4

3

1

2

3

2

2

3

11

01

00

**Over**

transfer function

of convolutional codes

1

2

3

4

5

6

7

8

**9**

**10**

11

12

13

**14**

15

16

**17**

18

**19**

**20**

21

**22**

1

0

1

1

0

0

1

0

0

1

input

bits

output

bits

memory's

states

00

01

00

01

11

10

00

01

00

01

11

10

11

10

**Non-commutative rings and their applications**

**Lens - July 1-4 2013**