FPGA Central

Hi,

I would appreciate it if someone could help me with the following: I
want to know how many groups of erasure distributions can occur for a
fixed amount of erasures for a cyclic block code.

As an example, say I have a cyclic block code with a total of 7
symbols and if an erasure occurred, there will always be 3 unknown
symbols, at arbitarily places x,y and z.

A. Because it is a cyclic code, I can cyclically shift the received
code such that there will always be an erasure in position c1, if the
code can be written as (c1,c2,c3,c4,c5,c6,c7).

B. Another consequence of the cyclic property is that a codeword with
erasures in c1,c2 and c7 can be shifted such that symbols c1,c2 and c3
of the new codeword is erased, thus, the two codewords have the same
erasure distribution (after shifting).

For the above case all the possible erasure positions for 3 erasures
is the following (c_x => received symbol, e_x => erased symbol)
(d = (y - x, z - y, x+n - z) is the distance between the erasures
where the erasures is (e_x, e_y, e_z)):

(e1, e2, e3, c4, c5, c6, c7) => d = (1, 1, 5) => g1
(e1, e2, c3, e4, c5, c6, c7) => d = (1, 2, 4) => g2
(e1, e2, c3, c4, e5, c6, c7) => d = (1, 3, 3) => g3
(e1, e2, c3, c4, c5, e6, c7) => d = (1, 4, 2) => g4
(e1, e2, c3, c4, c5, c6, e7) => d = (1, 5, 1) => g1

(e1, c2, e3, e4, c5, c6, c7) => d = (2, 1, 4) => g4
(e1, c2, e3, c4, e5, c6, c7) => d = (2, 2, 3) => g5
(e1, c2, e3, c4, c5, e6, c7) => d = (2, 3, 2) => g5
(e1, c2, e3, c4, c5, c6, e7) => d = (2, 4, 1) => g2

(e1, c2, c3, e4, e5, c6, c7) => d = (3, 1, 3) => g3
(e1, c2, c3, e4, c5, e6, c7) => d = (3, 2, 2) => g5
(e1, c2, c3, e4, c5, c6, e7) => d = (3, 3, 1) => g3

(e1, c2, c3, c4, e5, e6, c7) => d = (4, 1, 2) => g2
(e1, c2, c3, c4, e5, c6, e7) => d = (4, 2, 1) => g4

(e1, c2, c3, c4, c5, e6, e7) => d = (5, 1, 1) => g1

Thus, all erasure distributions can be grouped into 5 groups. Is
there maybe a mathematical equation that I can use to compute the
number of groups for a given number of symbols and a given number of
erasures?

Your time, effort and suggestions will be greatly appreciated
Jaco

Sorry about the typos - its been a bad week! The formulas were correct
however, the Englisg looked pretty bad.

Clay


Hello Jaco,

Since you have 7 syms with 3 errs and one error is always at the front,
then
you have 6 choose 2 combinations = 15

n choose k is calculated as n! / ( (n-k)! k! )

Since most of the numbers in the computation cancel out, to simply
calculate, just make a fraction where the
top counts down from N and the bottom counts down from k for k terms.

6*5 30
---- = --- = 15
2*1 2

Now since you are forming groups by rotations and you have k errors, then
there are k rotations per group (you have to have an error in the 1st
spot),
so the formula for the number of groups is (I make no guarantees)


n!
-----------
(k+1) (n-k)! k!

which when n=6 (#syms -1) and k=2 (#errs-1)

we find

6!
----------- = 5 groups
3 * 4! * 2!

I hope this helps.

Clay

"Clay S. Turner" wrote:
>
...
> however, the Englisg looked pretty bad. ...
>
It's been a bad week for me too.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Thanks a lot,

Jaco

"Clay S. Turner" <[email protected]> wrote in message news:<8HYKa.25557$[email protected] m>...
> Sorry about the typos - its been a bad week! The formulas were correct
> however, the Englisg looked pretty bad.
>
> Clay
>
>
> Hello Jaco,
>
> Since you have 7 syms with 3 errs and one error is always at the front,
> then
> you have 6 choose 2 combinations = 15
>
> n choose k is calculated as n! / ( (n-k)! k! )
>
> Since most of the numbers in the computation cancel out, to simply
> calculate, just make a fraction where the
> top counts down from N and the bottom counts down from k for k terms.
>
> 6*5 30
> ---- = --- = 15
> 2*1 2
>
> Now since you are forming groups by rotations and you have k errors, then
> there are k rotations per group (you have to have an error in the 1st
> spot),
> so the formula for the number of groups is (I make no guarantees)
>
>
> n!
> -----------
> (k+1) (n-k)! k!
>
> which when n=6 (#syms -1) and k=2 (#errs-1)
>
> we find
>
> 6!
> ----------- = 5 groups
> 3 * 4! * 2!
>
> I hope this helps.
>
> Clay

Hi,

Thanks for the reply.

As I understand it, the total number of groups will be:

total # of combinations / rotations per group,

where the total # of combinations is given by n! / ((n-k)! k!), where
n = (# of symbols - 1) and k = (# of erasures -1). The # of rotations
= # of erasures => k+1.

I have written a MATLAB program to verify the equation. For the
example in the NG, the equation works great, as we anticipated.

However, two questions that I have:


1.

When n^choose_k is not divisably by (k+1), what will happen? As an
example, if we have 12 symbols and 4 erasures, thus n^choose_k:

11^C_3 = 165,

165 / 4 = 41.25


However, a problem arises for the case when I have 10 symbols and 4
erasures.

n^choose_k = 9^C_3 = 84.

84/4 = 21 => thus, I should get 21 groups.

With the MATLAB program, I detect 22 groups.

The problem comes in with the assumption that each rotation will give
a different "erasure distribution".

As an example, consider erasures in positions (1, 4, 6, 9). d = (3, 2,
3, 2)
When d is rotated:
1x (2,3,2,3)
2x (3,2,3,2)
3x (2,3,2,3)

Thus, we only have 2 groups, where we should have got 3 different
groups...

How can this be fixed

Your time, effort and suggestions will be greatly appreciated
Jaco



> "Clay S. Turner" <[email protected]> wrote in message news:<8HYKa.25557$[email protected] m>...
> > Sorry about the typos - its been a bad week! The formulas were correct
> > however, the Englisg looked pretty bad.
> >
> > Clay
> >
> >
> > Hello Jaco,
> >
> > Since you have 7 syms with 3 errs and one error is always at the front,
> > then
> > you have 6 choose 2 combinations = 15
> >
> > n choose k is calculated as n! / ( (n-k)! k! )
> >
> > Since most of the numbers in the computation cancel out, to simply
> > calculate, just make a fraction where the
> > top counts down from N and the bottom counts down from k for k terms.
> >
> > 6*5 30
> > ---- = --- = 15
> > 2*1 2
> >
> > Now since you are forming groups by rotations and you have k errors, then
> > there are k rotations per group (you have to have an error in the 1st
> > spot),
> > so the formula for the number of groups is (I make no guarantees)
> >
> >
> > n!
> > -----------
> > (k+1) (n-k)! k!
> >
> > which when n=6 (#syms -1) and k=2 (#errs-1)
> >
> > we find
> >
> > 6!
> > ----------- = 5 groups
> > 3 * 4! * 2!
> >
> > I hope this helps.
> >
> > Clay

Hello Jaco,

Well I made no guarantees about the formula for the number of groups. At
least it gives an estimate. I'll think about the problem some more, and see
if there is a reasonable way to do it. Certainly having the computer count
the groups is not a bad idea unless you are planning on some very large
codeword sizes.

Clay

Thanks a lot,

Yip, what is very nice of the equation, is that it gives a lower
bound, so I will know what is the minimum of groups need.

Thanks for the time and effort
Jaco


"Clay S. Turner" <[email protected]> wrote in message news:<uaEMa.5898$[email protected]> ...
> Hello Jaco,
>
> Well I made no guarantees about the formula for the number of groups. At
> least it gives an estimate. I'll think about the problem some more, and see
> if there is a reasonable way to do it. Certainly having the computer count
> the groups is not a bad idea unless you are planning on some very large
> codeword sizes.
>
> Clay