SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011)

A Search Algorithm Based on SyndromeA Search Algorithm Based on SyndromeComputation to Get Efficient Shortened CyclicComputation to Get Efficient Shortened Cyclic

Codes Correcting either Random Errors or Codes Correcting either Random Errors or BurstsBursts

José René Fuentes Cortez, Ana Lucila Sandoval Orozco, Luis Javier

García Villalba and Mario Blaum

Universidad Complutense de Madrid

SPANISH CRYPTOGRAPHY SPANISH CRYPTOGRAPHY DAYSDAYS

(SCD 2011)(SCD 2011)

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011) 2

Introduction

Cyclic codes correcting even a single burst are difficult to obtain. Fire codes are a family of such codes, but better codes were obtained by computer search.

We are presenting an algorithm that optimizes the search of the best (shortened) single burst-correcting codes, using Gray codes to avoid the computation of repeated syndromes.

We use Gallagher efficiency, which allows for comparison between different types of single-burst-correcting codes, regardless of them being of either block or convolutional type.

Comparisons are based upon establishing a pair (b, g), where b is the length of the burst we want to correct and g is the guard space.

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011)

What is a Burst (b)?

Assume that an all-zero sequence is transmitted and let e0, e1 ,e2, … be the received sequence, i.e. 1s represent errors and 0s absence of errors. Then, a vector of b consecutives bits (e0, e1 ,e2, …) is called a burst of length b with respect to a guard space of length g:

Consider the following codes with n = 7 (n - length of the codeword)

Example: b = 3 → 1010000, 0000101, 0000111, 1110000 etc.

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011)

Non all around bursts (NAA): given a block of n bits e0, e1, e2, , , ,en -1, We say that e0, e1, e2, , , , en -1 is a NAA burst of length b, where b < n, if there is an l such that l + b ≤ n, el = el + b - n - 1 = 1 and ei = 0 for i < l or i > l + b - 1.

Example: b = 3 → 1010000, 0000001, 0000111, 1100000 etc.

Similarly, given a block of n bits e0, e1, e2, , , , en -1, we say that e0, e1, e2, , , , en -1, is an all around burst (AA) of length b, where 1 ≤ l ≤ n – 1 and b < n, if there is l + b > n, el = el + b - n - 1 = 1 and ei = 0 for l + b - n - 1 < i < l.

Example: b = 3 → 1000001, 0100001, 1100001, 1100000, etc.

Types of Bursts

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011)

Consider a pair (b, g) = (3, 8).

… 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0….

We can see that two consecutive bursts of length up to three (in red) are separated by at least 8 - 0s.

The value of b has to be associated to the value of g, and we associate a code C to a pair (b, g)GS is valid for both block and convolutional codes.How do we construct block codes [n, k] that satisfy the pair (b, g)? (k – dimension of the code)

g g g

b b b b

Guard Space (g)

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011)

Relation between guard space and length of a code

Assume that C is an [n, k] code capable of correcting any all around burst of length up to b. Then, the guard space is n - b. In the example below, n = 10 and b = 3, so g = 7.

… 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 …

Similarly, assume that C' is an [n’, k’] code capable of correcting any non – all around burst of length up to b, but not necessarily all-around bursts. Then, the guard space is at least n'-1. Below, n=10, so g = 9

…0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 …How do we decide between an all-around and a non-all-around shortened cyclic code?

n = 10 n = 10b = 3 b = 3

n = 10n = 10

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011) 7

Criterion to decide between the two

We will choose the code that has better rate, either k/n for C or k’/n’ for C'.

Assume that we want to correct bursts of length up to b with guard space at least g.

If C and C' are [n, k] and [n', k' ] all-around and non-all-around burst-correcting shortened cyclic codes respectively with this burst space g, by the discussion above, g = n - b and g = n‘ -1, therefore, n = n’+ b - 1.

We had presented this result at [5] of our paper.

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011) 8

Example (cyclic and shortened cyclic codes)

Consider a pair (b, g) = (3, 25). There is a shortened cyclic [28, 19, {3, 3}] (3, 25) burst-correcting code generated by x9 + x8 + x6 + 1. By computer search we can determine that there is no [28, 20, {3, 3}] burst-correcting (shortened) cyclic code. (all- around case)

Similarly, we find [26, 19, {3, 1}] (3, 25) burst-correcting shortened cyclic code but no [26, 20, {3, 1}] . (non – all – around case)

However, there is the [27, 20, {3, 2}] shortened cyclic code, which is generated by x7 + x6 + x3 + 1, is a (3, 25) burst-correcting shortened cyclic code and it has better rate than both the [28, 20, {3, 3}] and [26, 19, {3, 1}] codes.

So we proceed as follows; for a given (b, g), each l, 1 < l < b, we search an optimal [g + l, kl , {b, l}] burst-correcting code by using our search algorithm. R = kl / (g + l)

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011) 9

We check if there exists an [n, k, {b, l}] (shortened) cyclic code, 1 ≤ l ≤ b, we need to check all possible generator polynomials of degree n – k. If we find one, we stop the search. If there is none, then we try to find an [n, k – 1] code using the same procedure, and so on, until we determine the largest possible value of k.

In order to reduce our search, many polynomials can be eliminated from the search with a quick test.

We will again illustrate the algorithm with a particular example: we will take n = 14, b = 3 and g(x) = 1 + x3 + x4 + x5 + x6. Since g(x) has degree 6, this is a [14, 8] code that we denote by C. We will explore whether C is a {3, 2} or a {3, 3} single burst-correcting code using our search algorithm to be described next (by the Reiger bound, C cannot be a {4, l} single burst-correcting code).

Algorithm searching for optimal burst-correcting codes

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011) 10

First we get the generator matrix. Since the code has dimension 8, the generator matrix G is obtained by shifting g(x) in binary 8 times

Next, we get the parity-check matrix H from G. We put G in systematic form by Gaussian elimination. Once the Gaussian elimination process is finished, matrix G is transformed into the systematic form

Algorithm searching for optimal burst-correcting codes

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011) 11

When a systematic generator matrix has the form (Ik | V), with Ik the k x k identity matrix and V a k x (n – k) matrix, then a systematic parity-check matrix is given by H = (In – k | VT ), VT the transpose of V. Applying this formula to Gsys above, we obtain the systematic H:

Algorithm searching for optimal burst-correcting codes

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011) 12

Parity - check matrix

Algorithm searching for optimal burst-correcting codes

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011) 13

Consider the following error pattern ω1 with burst length b = 3;

For this particular case the syndrome s1 of ω1 is:

In other words, the syndrome of a burst of length at most b occurring in the last n – k coordinates is also a (NAA) burst of length at most b with respect to a systematic parity check matrix H

Finding the syndromes of NAA Bursts

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011) 14

The list of syndromes of burst of length up to 3 in the last coordinates together with their decimal representation

In general there are : 2b – 1(n – k – ( b – 2)) NAA

bursts of length up to b among the n – k corresponding to the syndromes.

Finding the syndromes of NAA Bursts

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011)

15

We keep in mind that we want to check if there exists an [n, k, {b, l}] if l > 1,we need to compute the syndromes AA bursts of length up to l.

If l = 2. This case is simple since there is only one AA burst of length exactly 2, which is:

It corresponding syndrome is: s4 = ω4 HT = (1 1 0 1 0 1) = 53

If l = 3. This case is simple since there is only one AA burst of length exactly 2, which is:

Finding the syndromes of AA Bursts

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011) 16

The corresponding syndromes s5, s6, s7, s8 of ω5, ω6, ω7 and ω8 are;

The set of syndromes (in decimal) corresponding to NAA bursts length up to 3 occurring in the last 6 (in general n – k) coordinates together with those corresponding to AA burst of length up to 3 we have seen is:

Finding the syndromes of AA Bursts

No All-Around bursts (NAA) AA

l = 3

l = 2

= 54

= 55

= 27

= 47

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011)

Now we have to examine the syndromes of all NAA bursts of length up to 3 by using Gray Codes and compare them with set S.

Gray Codes: The term “Gray code” is sometimes used to refer to any single-distance code, that is, one in which adjacent code words (perhaps representing integers differing by 1) differ by 1 in one digit position only.

We have to compute 32 syndromes of the 32 bursts starting in locations from 0 to 7 or what is from 0 to k – 1. In general are k2b – 1,by using the previous one XORing the one column of H at a time to previously found syndrome, minimizing the number of operations.

Using Gray Codes

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011)

One way to write such 32 bursts is as follows;

……………………………

Using Gray Codes

From 0

until k – 1

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011)

One way to find all syndromes is to compute each burst and multiply it to parity check matrix H. How is illustrate it.

Instead multiplying we use Gray codes to compute the syndromes by XORing the previously computed syndrome with columns:

2, 1, 2, 0, 3, 2, 3, 1, 4, 3, 4, 2, 5, 4, 5, 3, 6, 5, 6, 4, 7, 6, 7, 5, 8, 7, 8, 6, 9, 8, 9Verifying at each step if s in decimal is in S or not.

Using Gray Codes

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011)

Returning to our example, we see that;

……………………………

This last syndrome corresponds to the AA burst of length 3 as we have seen: ω6 = (1 0 0 0 0 0 0 0 0 0 0 0 1 1)

So the C is no [14, 8, {3, 3}]. Is the same code C [28, 19, {3, 2}]?

In this case the set of syndromes is reduced to:

Using Gray Codes

No All-Around bursts (NAA) AA

l = 2

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011)

Continuing with the search we obtain the following computation:

We can see that none of the syndromes is in S’ so C is a {b, l} = {3, 2} single burst-correcting code.

The general case is analogous to the one illustrated in this example.

Using Gray Codes

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011)

Tables of best burst-correcting codes

Optimal (shortened) cyclic codes correcting bursts of length up to 8, for a guard space from g = 20 to g = 60

……………………….

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011)

Tables of best burst-correcting codes

Optimal (shortened) cyclic codes correcting bursts of length up to 9, for a guard space from g = 61 to g = 100

……………………….

SPANISH CRYPTOGRAPHY DAYS (SCD 2011)SPANISH CRYPTOGRAPHY DAYS (SCD 2011)

Conclusions

We have presented an efficient algorithm finding the best cyclic single-burst-correcting codes for different parameters.

We were able to optimize the parameters of shortened cyclic burst-correcting codes by minimizing the number of syndrome checks using Gray codes.

Extensive tables with the most efficient codes have been presented.