Author Topic: Practical guides to BCH FEC?  (Read 3246 times)

0 Members and 1 Guest are viewing this topic.

Offline hamster_nzTopic starter

  • Super Contributor
  • ***
  • Posts: 2803
  • Country: nz
Practical guides to BCH FEC?
« on: June 21, 2018, 08:19:59 am »
Does anybody have any knowledge or links to practical guides to error correction using BCH codes?

I am comfortable with generating them (they are much like CRCs) but it is the correction side I am interested in.

As far as I understand you try to verify them, much the same as a CRC, and the remainder indicates what errors (if any) exist.

Do I just need to make a lookup table mapping remainder to flipped bits, or does a far more subtle or efficient method exist for correcting the errors?

P S. Looking to implement in a FPGA pipeline

« Last Edit: June 21, 2018, 08:27:26 am by hamster_nz »
Gaze not into the abyss, lest you become recognized as an abyss domain expert, and they expect you keep gazing into the damn thing.
 

Offline coppice

  • Super Contributor
  • ***
  • Posts: 8605
  • Country: gb
Re: Practical guides to BCH FEC?
« Reply #1 on: June 21, 2018, 10:10:11 am »
If you are using a code which allows correction on only 1 bit, decoding is pretty easy. If you try generating some codes, flipping a bit, and looking at the resulting decoded syndrome you should be able to see how that works out. If you are using a code which allows the correction of multiple bits, things get a bit more complex. There is quite a bit of information on the web about processing BCH codes.
 

Offline hamster_nzTopic starter

  • Super Contributor
  • ***
  • Posts: 2803
  • Country: nz
Re: Practical guides to BCH FEC?
« Reply #2 on: June 21, 2018, 11:44:33 am »
If you are using a code which allows correction on only 1 bit, decoding is pretty easy. If you try generating some codes, flipping a bit, and looking at the resulting decoded syndrome you should be able to see how that works out. If you are using a code which allows the correction of multiple bits, things get a bit more complex. There is quite a bit of information on the web about processing BCH codes.

About the best I have found that hints at a H/W decoder is this: http://ijcsma.com/publications/may2014/V2I517.pdf


Rather than matrix math and linear algebra, it has something that might result in a reasonable H/W implementation (see snipped image)
Gaze not into the abyss, lest you become recognized as an abyss domain expert, and they expect you keep gazing into the damn thing.
 

Offline hamster_nzTopic starter

  • Super Contributor
  • ***
  • Posts: 2803
  • Country: nz
Re: Practical guides to BCH FEC?
« Reply #3 on: June 22, 2018, 12:38:52 pm »
Leaving a breadcrumb for anybody who follows...

I've got a BCH decoder that works for for the BCH codes used on HDMI data packets.

If you have the data (maybe with an error in it), calculate the BCH parity of the 24 data bits. then XOR the received parity bits with the freshly calculated parity bits to get "error".

The pass the received data and the parity error through the following code to correct the data:

Code: [Select]
unsigned bch_solve(unsigned data, unsigned error) {
  int i;
  unsigned result = 0;

  for(i = 0; i < 32; i++) {
     /* Produce the next corrected bit in the high bit of result */
     result = result >> 1;
     if(error == 0x4A) {
        error ^= 0x4A;
        result |= (~data)<<31;
     } else {
        result |= data<<31;
     }
     data = data>>1;

     /* Unwind the parity */
     if(error & 0x1) {
        error  = error >> 1;
        error ^= 0x83;
     } else {
        error  = error >> 1;
     }
  }
  return result;
}
Am testing it overnight with all possible single bit error (16M different data values, and 32 possible errors), but a million random test vectors worked OK.

Logic is funky as it is structured to use in testing an FPGA implementation where the bits stream through it - and yes, it assumes 'unsigned'  is a 32-bit values.
Gaze not into the abyss, lest you become recognized as an abyss domain expert, and they expect you keep gazing into the damn thing.
 

Offline coppice

  • Super Contributor
  • ***
  • Posts: 8605
  • Country: gb
Re: Practical guides to BCH FEC?
« Reply #4 on: June 22, 2018, 01:03:34 pm »
Leaving a breadcrumb for anybody who follows...

I've got a BCH decoder that works for for the BCH codes used on HDMI data packets.

If you have the data (maybe with an error in it), calculate the BCH parity of the 24 data bits. then XOR the received parity bits with the freshly calculated parity bits to get "error".

The pass the received data and the parity error through the following code to correct the data:

Code: [Select]
unsigned bch_solve(unsigned data, unsigned error) {
  int i;
  unsigned result = 0;

  for(i = 0; i < 32; i++) {
     /* Produce the next corrected bit in the high bit of result */
     result = result >> 1;
     if(error == 0x4A) {
        error ^= 0x4A;
        result |= (~data)<<31;
     } else {
        result |= data<<31;
     }
     data = data>>1;

     /* Unwind the parity */
     if(error & 0x1) {
        error  = error >> 1;
        error ^= 0x83;
     } else {
        error  = error >> 1;
     }
  }
  return result;
}
Am testing it overnight with all possible single bit error (16M different data values, and 32 possible errors), but a million random test vectors worked OK.

Logic is funky as it is structured to use in testing an FPGA implementation where the bits stream through it - and yes, it assumes 'unsigned'  is a 32-bit values.
Well done. Most BCH codes decode with something simple like that. If you look at early uses of BCH codes, they had to be implemented with very few gates. Things like the Golay and POCSAG radiopaging codes couldn't afford either the gates or the power consumption of a complex lookup table scheme, so they were forced to chose BCH codes which could be implemented as simply as the one you have decoded. These days more gates aren't an issue, but it you want to run at HDMI speeds using a code that permits simple decoding is still a wise choice.
 

Offline philpem

  • Frequent Contributor
  • **
  • Posts: 335
  • Country: gb
  • That Sneaky British Bloke
Re: Practical guides to BCH FEC?
« Reply #5 on: July 23, 2018, 01:35:52 pm »
I'm curious -- what is the significance of 0x4A and 0x83? (I'm guessing 0x4A is the generator polynomial?)

I'm trying to modify this for the (31,21) BCH code used by POCSAG. Looks like this would be fairly efficient to implement on an MCU, or at least have a predictable execution time.
Phil / M0OFX -- Electronics/Software Engineer
"Why do I have a room full of test gear? Why, it saves on the heating bill!"
 

Offline coppice

  • Super Contributor
  • ***
  • Posts: 8605
  • Country: gb
Re: Practical guides to BCH FEC?
« Reply #6 on: July 23, 2018, 07:03:27 pm »
I'm curious -- what is the significance of 0x4A and 0x83? (I'm guessing 0x4A is the generator polynomial?)

I'm trying to modify this for the (31,21) BCH code used by POCSAG. Looks like this would be fairly efficient to implement on an MCU, or at least have a predictable execution time.
I should still have code for full commercial grade POCSAG encoding and decoding software somewhere, that used to run on MSDOS machines. I don't think there is anything in there which would stop me from open sourcing it, if anyone were interested. It certainly has no commercial value these days.
 

Offline philpem

  • Frequent Contributor
  • **
  • Posts: 335
  • Country: gb
  • That Sneaky British Bloke
Re: Practical guides to BCH FEC?
« Reply #7 on: July 24, 2018, 11:54:26 am »
I'd certainly be interested in seeing the decoder side!

Encode is easy, it's fixing errors in the received data that's hard!
Phil / M0OFX -- Electronics/Software Engineer
"Why do I have a room full of test gear? Why, it saves on the heating bill!"
 

Offline coppice

  • Super Contributor
  • ***
  • Posts: 8605
  • Country: gb
Re: Practical guides to BCH FEC?
« Reply #8 on: July 24, 2018, 01:30:38 pm »
I'd certainly be interested in seeing the decoder side!

Encode is easy, it's fixing errors in the received data that's hard!
I found my encoder source code, but it looks like my off air monitor code must be on a 5.25" floppy which I no longer have the ability to read. A quick Google for POCSAG finds a surprising amount of open source activity for something so obsolete. Most seem to decode in a clumsy, brute force, manner - e.g. MultiMon-NG - freely admitting that they are using a clumsy approach. On pages 50 and 51 of the paper hamster-nz referenced they describe the "canonical" approach - the sort of thing Mr B, Mr C and Mr H had in mind, and which hardware POCSAG decoder used to do in a handful of 0.9V low power gates. Their diagrams aren't the clearest, but between the diagrams and the text they convey the idea. As the bits flow through the hardware the receive side should track what happened at the transmit side. Where it doesn't (i.e. the generated state doesn't agree with the received state), there has been a bit error, and the currently processed bit needs to be swapped. 30 years ago, implementing this in the heyday of POCSAG, I found a more efficient scheme for software implementation. Instead of checking bit by bit I was able to arrive at actual bit numbers which were in error, and then I just flipped those. I really can't remember the details of how that worked, though.
 
The following users thanked this post: philpem

Offline philpem

  • Frequent Contributor
  • **
  • Posts: 335
  • Country: gb
  • That Sneaky British Bloke
Re: Practical guides to BCH FEC?
« Reply #9 on: July 27, 2018, 08:37:13 am »
I expect you could do it really quickly on a modern MCU by storing the syndrome values which correlate errors to bit positions.

For POCSAG you have a (31,21,2) BCH -- so 21 data bits, 10 BCH bits and an overall parity bit.
I'm not certain what good the parity bit is, as you can't easily (AIUI) tell if there's an error in the parity bit. I guess on its own it's good to guarantee you can't have a codeword of all the same bit (which PLL based FSK/FM transmitters won't like, you'll lose modulation as it's AC-coupled).

Back to BCH...

If you have 10 BCH bits, by definition you have 2^10=1024 possible syndromes.
BCH + Data is 31 bits, which means you need a 32-bit integer to store the error mask (XOR mask).

You have 31 possible 1-bit errors and (31*30)=930 2-bit errors, giving 961 entries in a 1024-entry table.

So there's what, a 6.25% chance of detecting an N>=3 bit error?   ((930-1024)/1024)

If you get an error burst at the end of the CW - it's likely to knock out the parity bit too. So you can't rely on parity to tell you if the CW was corrected OK...

 :-//

I'll have to have another go at modifying hamster_nz's code to work on a POCSAG codeword...

EDIT:  Answering my own question --
  0x83 (0b10000011) is the HDMI Generator Polynomial expressed in binary (G(x)=1+x^6+x^7+x^8
  0x4A (0b01001010) is the syndrome value when there is an error in the current data bit.
Look at this in the context of Ross Williams' CRC code and things start to make more sense!
« Last Edit: July 27, 2018, 10:26:15 am by philpem »
Phil / M0OFX -- Electronics/Software Engineer
"Why do I have a room full of test gear? Why, it saves on the heating bill!"
 

Offline coppice

  • Super Contributor
  • ***
  • Posts: 8605
  • Country: gb
Re: Practical guides to BCH FEC?
« Reply #10 on: July 27, 2018, 10:42:12 am »
I expect you could do it really quickly on a modern MCU by storing the syndrome values which correlate errors to bit positions.

For POCSAG you have a (31,21,2) BCH -- so 21 data bits, 10 BCH bits and an overall parity bit.
I'm not certain what good the parity bit is, as you can't easily (AIUI) tell if there's an error in the parity bit. I guess on its own it's good to guarantee you can't have a codeword of all the same bit (which PLL based FSK/FM transmitters won't like, you'll lose modulation as it's AC-coupled).

Back to BCH...

If you have 10 BCH bits, by definition you have 2^10=1024 possible syndromes.
BCH + Data is 31 bits, which means you need a 32-bit integer to store the error mask (XOR mask).

You have 31 possible 1-bit errors and (31*30)=930 2-bit errors, giving 961 entries in a 1024-entry table.

So there's what, a 6.25% chance of detecting an N>=3 bit error?   ((930-1024)/1024)

If you get an error burst at the end of the CW - it's likely to knock out the parity bit too. So you can't rely on parity to tell you if the CW was corrected OK...

 :-//

I'll have to have another go at modifying hamster_nz's code to work on a POCSAG codeword...
I think the parity bit was put there to allow crude tone only pagers to do nothing more than a parity check with the simplest of possible logic. Since tone pager only decode a single codeword for each message, and the result is match or not match, parity is quite effective at reducing false positives. The parity bit is another check on the data, and does increase the number of errors you can pick up, beyond what the BCH code can do. If the BCH is clean and the parity bit is in error, then for an information codeword I would ignore the parity error, but for an address codeword I would conclude the codeword cannot be trusted. People really wanted the false positive rate to be low. I think most pagers used the parity on address codewords, and not on information codewords.

The 1024 entry table approach you describe is probably the most effective solution on a device with enough memory. However, I do remember working out an algorithmic approach that gave the same sort of result as such a table.

Most large scale paging transmitters were not simply AC coupled FM designs. Ones that were tended to be quite troublesome in single transmitter setups, and were hopeless in simulcast setups. Most applied some form of digital trickery in a PLL to avoid long strings of ones or zeros from sending the transmission off frequency. I never saw a pager that wasn't AC coupled, though, so you couldn't send ones or zeros forever, and get the right effect at the receiver.
 

Offline philpem

  • Frequent Contributor
  • **
  • Posts: 335
  • Country: gb
  • That Sneaky British Bloke
Re: Practical guides to BCH FEC?
« Reply #11 on: July 27, 2018, 09:24:12 pm »
I hadn't considered that possibility for tone-only! Of course in 1980s tech you'd want to simplify this as much as possible to keep the physical size, cost and power consumption down. Then for numeric and alphanumeric you add the error correction in.

Here's my crack at an algorithmic solution based on hamster_nz's.

It includes POCSAG BCH encoding (including parity) and decoding of one- and two-bit errors, with unit tests using the Unity framework (https://www.throwtheswitch.org/unity).
It claims to be C++ but is really just "C with a bit of C++").

I welcome suggestions for optimisation, it certainly isn't optimal!

Note that if all you want to do is correct single-bit errors, you only need one syndrome comparator.
If you want to correct double-bit errors too, you're going to need a syndrome comparison for every possible error combination. So for a (31,21) BCH with two-bit correction capability, that's 31 syndrome comparisons.

If you want to correct three bit errors, you're looking at somewhere in the region of 900 comparisons, at which point table lookup may be more practical. Depends if you can find a good way to store a fairly sparse table in an easily-accessible way. A map or sorted array might be a good option.

I'm going to be travelling for a while tomorrow so I might give the table lookup optimisation a shot!
« Last Edit: July 27, 2018, 09:26:31 pm by philpem »
Phil / M0OFX -- Electronics/Software Engineer
"Why do I have a room full of test gear? Why, it saves on the heating bill!"
 
The following users thanked this post: srce

Online amyk

  • Super Contributor
  • ***
  • Posts: 8240
Re: Practical guides to BCH FEC?
« Reply #12 on: July 28, 2018, 04:56:59 am »
Well done. Most BCH codes decode with something simple like that. If you look at early uses of BCH codes, they had to be implemented with very few gates. Things like the Golay and POCSAG radiopaging codes couldn't afford either the gates or the power consumption of a complex lookup table scheme, so they were forced to chose BCH codes which could be implemented as simply as the one you have decoded. These days more gates aren't an issue, but it you want to run at HDMI speeds using a code that permits simple decoding is still a wise choice.
:-+ If more people were shown code like this when learning about RS/BCH/CRCs instead of highly theoretical number theory and abstract algebra, I bet the world would be a better place. Of course understanding the "why" is important and probably does require a bit more theory, but I think it's important to see that the practice is actually quite simple.

A related article along those lines is https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders#BCH_codes

Data compression is another area where the theory often obscures and smothers the practice.
 

Offline coppice

  • Super Contributor
  • ***
  • Posts: 8605
  • Country: gb
Re: Practical guides to BCH FEC?
« Reply #13 on: July 28, 2018, 07:51:13 am »
Well done. Most BCH codes decode with something simple like that. If you look at early uses of BCH codes, they had to be implemented with very few gates. Things like the Golay and POCSAG radiopaging codes couldn't afford either the gates or the power consumption of a complex lookup table scheme, so they were forced to chose BCH codes which could be implemented as simply as the one you have decoded. These days more gates aren't an issue, but it you want to run at HDMI speeds using a code that permits simple decoding is still a wise choice.
:-+ If more people were shown code like this when learning about RS/BCH/CRCs instead of highly theoretical number theory and abstract algebra, I bet the world would be a better place. Of course understanding the "why" is important and probably does require a bit more theory, but I think it's important to see that the practice is actually quite simple.

A related article along those lines is https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders#BCH_codes

Data compression is another area where the theory often obscures and smothers the practice.
Most articles on RS, BCH, and CRCs focus on hardware register implementations much more than the maths, for 3 good reasons:
  • Its much easier to see how they really work by looking at a register diagram. The maths doesn't really jump out at you, until you look at a register implementation.
  • The most common practical implementations of these codes are in hardware. The articles map directly to what most people need to build.
  • Software really obscures what is going on. To get any understanding from the code you need to map it back to how the bits would flow through a set of registers.
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf