The number of correctable errors
of weight d/2+1
for the 1st-order Reed-Muller code
Kenji Yasunaga
Information security engineering laboratory
Osaka University
Error Correcting Codes

Can correct errors in channels by adding
redundancy to message
Send
Sender
Message
Message
Redundancy
Coding
Channel
Same?
Errors !
Receiver
Output
Decoding
Receive
2
Error Correction Capability
d : the minimum distance of the code
w(e) = #(corrupted bits in error e)

If w(e) < d/2 ⇒ Always correctable!
If w(e) ≥ d/2 ⇒ ??
 Analysis for w(e) ≥ d/2 is a difficult problem
In this work,
we investigate #(correctable errors e for w(e) ≥ d/2)
3
Main results

#(correctable errors of w(e)=d/2+1) for the
1st-order Reed-Muller codes is derived

Probably the first nontrivial result of the exact
number for w(e)=d/2+1 for error correcting codes
Main technique
 Monotone error structure


Already appeared in [Peterson, Weldon, 1972]
But there is only few research using this structure
• We show the usefulness of this structure
4
Monotone error structure (1/2)
We introduce covering relation for vectors
x⊆y

⇔
xi ≤ yi for all i
Example
000 ⊆ 001 ⊆ 011 ⊆ 111
0000 ⊆ 0110 ⊆ 1110 ⊆ 1111
5
Monotone error structure (2/2)
x is correctable ⇒ all y s.t. y ⊆ x are correctable
x is uncorrectable ⇒ all y s.t. x ⊆ y are uncorrectable
0000
x⊆y
⇔
x
y
0011
Correctable errors
0001 0010 0100 1000
0101
0110
1001
1010
1100
0111 1011 1101 1110
The code is {0000, 1111}.
Uncorrectable errors
1111
6
The result
m 1
m




2
2
1
m
m 3
m2
  (4  3) 
 | Ed / 21 (RM m ) | 4(2  1)(2  1) m2

3
2

1


 
Uncorrectable errors
m


2
0
1
| Ed / 21 (RM m ) |  | Ed / 21 (RM m ) |   m2 
 2  1
Correctable errors
7
Very very short proof sketch
E1d/2+1(RMm)
Wm
|Wm| is easily obtained

We determine this size
by 5-page proof
Wm = { v : v ⊆ c for c ∈ RMm〵{0,1}, w(v)=d/2+1}
m


2
m
|Wm| = 2(2  1) m  2 
 2  1
8

Further Suggested Problems for Chapter 4

Inverse Domination Numbers and Disjoint Domination

Sheet 1 - Hu

110AH - GROUP THEORY TOPICS (FALL 2013) Contents 1