octave-dev

[OctDev] More limitations in coding functions

[Quentin S. <qsp...@ie...>]

This time I tried:
decode(x,255,247,'hamming')
and received the following error message:
error: syndtable: message and codeword length must be less than 32
error: evaluating assignment expression near line 248, column 5
error: evaluating if command near line 245, column 7
error: evaluating if command near line 203, column 5
error: evaluating if command near line 188, column 3
error: called from `decode' in file 
`/usr/share/octave/2.1.57/site/m/octave-forge/comm/decode.m'

So, it appears some modification of the syndtable function is necessary 
to make this work for hamming codes larger than the (31,36) code.

-Quentin

Re: [OctDev] More limitations in coding functions

[David B. <Dav...@mo...>]

Reading the comment in syndtable.cc 

  // Could convert this to unsigned long long, but there isn't much point.
  // the syndrome table can already have 2^32 rows with n columns, which
  // is already unrealistically large. The result is DON'T use this with
  // large BCH codes!!!!

you'll see why this limitation exists. In fact the problem is not the
syndrome table itself, but the calculation of all possible ways to have
n bit errors in a codeword which can be extremely large. I imagine there
is a better way to calculate the syndrome table and in fact until this
constraint is relaxed BCH and RS codes are the best bet :-) ...

If you have any better way to calculate the syndrome table I'd be
happy to get some advice..

D.
-- 
David Bateman                                Dav...@mo...
Motorola CRM                                 +33 1 69 35 48 04 (Ph) 
Parc Les Algorithmes, Commune de St Aubin    +33 1 69 35 77 01 (Fax) 
91193 Gif-Sur-Yvette FRANCE

The information contained in this communication has been classified as: 

[x] General Business Information 
[ ] Motorola Internal Use Only 
[ ] Motorola Confidential Proprietary

Re: [OctDev] More limitations in coding functions

[David B. <Dav...@mo...>]

Quentin,

Try the version I just committed. I removed the restriction on
calculating the minimum distance and vastly accelerated this code, and
I reduced the restriction on the syndrome table. There is still a
restriction at the moment in that the syndrome table must not have
more than 2^32 rows. This is enormous, and so I don't think I'll both
removing this restriction, and more memory than any machine I have access
to.

The code I used to test with was

1;
fprintf("  Hamming Coding:                           ");
nsym = 100;
m = 8;
[par, gen, n, k] = hammgen (m);
if (any(any(gen2par(par) != gen)))
  error("FAILED");
endif
if (gfweight(gen) != 3)
  error("FAILED");
endif
msg = randint(nsym,k);
code = encode(msg,n,k,"hamming");
noisy = mod(code + randerr(nsym,n), 2);
dec = decode(noisy,n,k,"hamming");
if (any(any(dec != msg)))
  error("FAILED");
endif         
try			# Protect! If bitshift isn't install!!
  msg = randint(nsym,1,n);
  code = encode(msg,n,k,"hamming/decimal");
  noisy = mod(code + bitshift(1,randint(nsym,1,n)), n+1);
  dec = decode(noisy,n,k,"hamming/decimal");
  if (any(dec != msg))
    error("FAILED");
  endif
catch
end
fprintf("PASSED\n");

The gfweight call still takes a while with m=8, so you might prefer to disable
it. I believe this removes all of the restrictions on the comms toolbox.

Cheers
David

According to Quentin Spencer <qsp...@ie...> (on 07/08/04):
> This time I tried:
> decode(x,255,247,'hamming')
> and received the following error message:
> error: syndtable: message and codeword length must be less than 32
> error: evaluating assignment expression near line 248, column 5
> error: evaluating if command near line 245, column 7
> error: evaluating if command near line 203, column 5
> error: evaluating if command near line 188, column 3
> error: called from `decode' in file 
> `/usr/share/octave/2.1.57/site/m/octave-forge/comm/decode.m'
> 
> So, it appears some modification of the syndtable function is necessary 
> to make this work for hamming codes larger than the (31,36) code.
> 
> -Quentin
> 
> 
> 
> -------------------------------------------------------
> This SF.Net email sponsored by Black Hat Briefings & Training.
> Attend Black Hat Briefings & Training, Las Vegas July 24-29 - 
> digital self defense, top technical experts, no vendor pitches, 
> unmatched networking opportunities. Visit www.blackhat.com
> _______________________________________________
> Octave-dev mailing list
> Oct...@li...
> https://lists.sourceforge.net/lists/listinfo/octave-dev

-- 
David Bateman                                Dav...@mo...
Motorola CRM                                 +33 1 69 35 48 04 (Ph) 
Parc Les Algorithmes, Commune de St Aubin    +33 1 69 35 77 01 (Fax) 
91193 Gif-Sur-Yvette FRANCE

The information contained in this communication has been classified as: 

[x] General Business Information 
[ ] Motorola Internal Use Only 
[ ] Motorola Confidential Proprietary

Re: [OctDev] More limitations in coding functions

[Quentin S. <qsp...@ie...>]

David Bateman wrote:

>Quentin,
>
>Try the version I just committed. I removed the restriction on
>calculating the minimum distance and vastly accelerated this code, and
>I reduced the restriction on the syndrome table. There is still a
>restriction at the moment in that the syndrome table must not have
>more than 2^32 rows. This is enormous, and so I don't think I'll both
>removing this restriction, and more memory than any machine I have access
>to.
>  
>
It works! I did some quick speed tests and got times just slightly 
faster (~5%) than Matlab 6.5.

-Quentin

Re: [OctDev] More limitations in coding functions

[David B. <Dav...@mo...>]

According to Quentin Spencer <qsp...@ie...> (on 07/16/04):
> David Bateman wrote:
> 
> >Quentin,
> >
> >Try the version I just committed. I removed the restriction on
> >calculating the minimum distance and vastly accelerated this code, and
> >I reduced the restriction on the syndrome table. There is still a
> >restriction at the moment in that the syndrome table must not have
> >more than 2^32 rows. This is enormous, and so I don't think I'll both
> >removing this restriction, and more memory than any machine I have access
> >to.
> > 
> >
> It works! I did some quick speed tests and got times just slightly 
> faster (~5%) than Matlab 6.5.

Humm, 5% faster is a bit of a slippery number. The octave code uses a DLD
for the calculation of the syndrome table and a dot-m file for the rest.
Matlab uses dot-m for everything. So is the 5% faster just for the calculation
of the syndrome? Or is it for the encode/decode? If its the second then I'm
happy, since the speed is then comaprable. If it is the first, I'm less happy
since on longer decodes octave will probably loose out.

D.

-- 
David Bateman                                Dav...@mo...
Motorola CRM                                 +33 1 69 35 48 04 (Ph) 
Parc Les Algorithmes, Commune de St Aubin    +33 1 69 35 77 01 (Fax) 
91193 Gif-Sur-Yvette FRANCE

The information contained in this communication has been classified as: 

[x] General Business Information 
[ ] Motorola Internal Use Only 
[ ] Motorola Confidential Proprietary