Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Noncommutative convolutional codes over the infinite dihedral group

No description
by

Marion Candau

on 4 September 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Noncommutative convolutional codes over the infinite dihedral group

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

Example
000
001
010
011
100
101
110
111

000
001
010
011
100
101
110
111

000
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

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
Full transcript