I have an RF module that is sending four bits of FEC per one byte of data (FEC is interleaved) and am having difficulty identifying what type of FEC it is using. I was hoping someone could steer me in the right direction so I can narrow down the possibilities. Are there any particular encoding schemes that come to mind that use four FEC bits per data byte? As an example:

0x4B is input to the module's microcontroller, and 0x87F is output to RF circuitry for transmission. Apparently 0x4B is being Xor'd with 0xAA then reversed (LSB-to-MSB) to get 0x87 (or reversed first then Xor'd with 0x55), but I can't figure out how the 0xF (FEC) is being computed.

 

I have an RF module that is sending four bits of FEC per one byte of data (FEC is interleaved) and am having difficulty identifying what type of FEC it is using. I was hoping someone could steer me in the right direction so I can narrow down the possibilities. Are there any particular encoding schemes that come to mind that use four FEC bits per data byte? As an example:

0x4B is input to the module's microcontroller, and 0x87F is output to RF circuitry for transmission. Apparently 0x4B is being Xor'd with 0xAA then reversed (LSB-to-MSB) to get 0x87 (or reversed first then Xor'd with 0x55), but I can't figure out how the 0xF (FEC) is being computed.

About all that can be said for sure is that you have a 2/3 rate code - meaning that two data bits are conveyed for each three bits transmitted.

I doubt that the codeword generation is done as you describe since it would provide no error correction capability. You can test this by simply checking a few other input-output pairs.

There are numerous FEC coding schemes. In some of them the data bits are kept intact and the additional parity check bits are used for correction. In others, the bits in the codeword are each a function of many (or even all) of the bits in the data word.

 

I should emphasize that the 8-bit data byte is transmitted followed by four FEC bits, followed by the next 8-bit data byte and FEC, etc., as follows:

Example:
Data Stream (hex) = 86 86 86 86
FEC (hex) = C

Transmitted Information: 86C 86C 86C 86C

Any idea as to which FEC schemes I should look at first given this example?

 

I should emphasize that the 8-bit data byte is transmitted followed by four FEC bits, followed by the next 8-bit data byte and FEC, etc., as follows:

Example:
Data Stream (hex) = 86 86 86 86
FEC (hex) = C

Transmitted Information: 86C 86C 86C 86C

Any idea as to which FEC schemes I should look at first given this example?

Unfortunately, all this really emphasizes is that neither description you've given can be correct. You've given two examples:

4B -> 87F
86 -> 86C

The first time you said that the data is XORed with something and then reversed (or possibly the other way around) to get the first two nibbles and the second time you said that the data is transmitted without modification as the first two nibbles. Well, neither of these are consistent with both examples.

Instead of trying to get someone to guess at something that has literally countless possible answers, why don't you tell us what RF module it is that you are using? It is far more likely that someone will be able to track down some documentation -- or give you a good suggestion on how to track it down yourself -- that will tell you what FEC protocol is being used.

Are you sure this is even FEC as opposed to a checksum or some other error detection scheme? I don't know if you can get 1 bit of FEC in a 12/8 code. You need it so that any of the 12 possible bit errors affects a unique set of the parity bits. This looks possible in theory, since there are 15 such sets, but I don't know if you can also meet the requirement that the 12-bit codeword must have a Hamming distance of at least three from any of the other 255 codewords.

 

Sorry, I was giving the over-data in my last example. The reversing and Xor-ing has already been applied. I am at work and fired off my last message quickly. I cannot reveal what the module is. Here are some more examples:

Baseband Data (hex): 01 01 01 01
Over-Air Data (hex): D5B D5B D5B D5B

Baseband Data (hex): 4B 4B 4B 4B
Over-Air Data (hex): 87F 87F 87F 87F

Baseband Data (hex): 5F 5F 5F 5F
Over-Air Data (hex): AFE AFE AFE AFE

Baseband Data (hex): DA DA DA DA
Over-Air Data (hex): 0E9 0E9 0E9 0E9

 

It's unlikely we will be able to help you. About the only shot we would have would be an exhaustive examination (or something approaching it). Fortunately, since there are only 256 codewords in a space of 4096 vectors, this is quite feasible. But you would have to enumerate all 256 codewords (again, not too difficult).

I could then analyze them to see if the thing is actually an FEC at all. If it is, I could map out which bits affect which parity bits and, from that, derive some kind of algorithm to perform the error correction. Whether or not I can back out of all it the actual matrices used (assuming it is a linear code) I don't know.

But be aware I would only be willing to make the attempt because the problem interests me. In general, expecting someone to do that much work for free is unreasonable.

 

Fair enough. I'm basically trying to figure it out out of curiosity as well and didn't expect anyone to spend too much effort on it. I was hoping for a simple answer but now understand that it isn't so simple. I have a datasheet, but all it says is that the module uses an "FEC mechanism" to enhance communication reliability. It is worth noting that the module also has acknowledge functionality, so perhaps it is really just has error detection with acknowledge (why would you need to acknowledge the transmission if you have error correction?). It is a cheap Taiwanese module and the spec sheet could very well be overstated to make the module more appealing.

 

There are a few reasons why it might support acknowledgement capability. FIrst, the other end of the link might require it. Second, if you don't try to correct errors, then you can detect at least twice as many bit errors.

If you can provide the 256 codewords, I would be happy to play with it at least a little.

 

Unfortunately, I don't have all 256 codewords, I only have seven. I no longer have the module, but can see if I can get it back. I'll let you know one way or the other. And if I didn't make this clear, it doesn't make a difference if I send one byte or 10, the error correction/detection nibble does not change for a given byte. I arbitrarily chose four bytes for my example. This is what I have at this point:

Raw Data (hex): 01 01 01 01
Encoded Data (hex): D5B D5B D5B D5B
Raw Data (hex): 4B 4B 4B 4B
Encoded Data(hex): 87F 87F 87F 87F
Raw Data (hex): 5F 5F 5F 5F
Encoded Data (hex): AFE AFE AFE AFE
Raw Data (hex): DA DA DA DA
Encoded Data (hex): 0E9 0E9 0E9 0E9
Raw Data (hex): 04 04 04 04
Encoded Data (hex): 75F 75F 75F 75F
Raw Data (hex): CB CB CB CB
Encoded Data (hex): 86C 86C 86C 86C
Raw Data (hex): D7 D7 D7 D7
Encoded Data (hex): BE8 BE8 BE8 BE8

 

Forgot, I have one more at this time:

Raw Data (hex): 55 55 55 55
Encoded Data (hex): FFC FFC FFC FFC

I will be getting the module back this Friday and will get all 256 code words for you (may take me a couple days). Thanks!

 

0x4B is input to the module's microcontroller, and 0x87F is output to RF circuitry for transmission. Apparently 0x4B is being Xor'd with 0xAA then reversed (LSB-to-MSB) to get 0x87 (or reversed first then Xor'd with 0x55),

Put another way, the data is input LSB-to-MSB (serial 8N1 format) and either Xor'd with 0xAA and reversed MSB-to-LSB prior to transmission, or reversed MSB-to-LSB first then Xor'd with 0x55 prior to transmission.

Does it make more sense for a modem's microcontroller to reverse the bits MSB-to-LSB first then perform the FEC calculation or do the calculation first then reverse the bits?

The "Raw Data" I listed in prior posts is actually listed LSB-to-MSB (e.g. 0x01 should actually be 0x80). In order of transmission (left-to-right), this is an example of what I have:

Firmware data: 0x80
8N1 interface data: 0 0 0 0 0 0 0 0 1 1 (start bit = 0, stop bit = 1)
Over-air data (encoded byte + FEC nibble): 0xD5B

Sorry for the confusion.

 

Here is some more data (55 codewords total). I will try to get the remaining code words to you by Friday or Monday.

00    55C
02    573
0B    5EB
0E    5B4
1B    4EE
20    75F
22    779
27    726
28    7D4
2E    7BE
36    630
3B    6E4
3C    69D
3F    6A8
4C    195
4E    1B3
52    071
54    01B
55    008
58    0DC
5B    0E9
5C    090
63    36D
66    332
6F    3AA
71    24E
80    D5B
89    DC3
8B    DE5
8F    DA9
90 C5E
9A    CF3
9E    CBF
9F    CAC
A6    F3B
A8    FDA
AA    FFC
AC    F96
B1    E47
B7    E2D
BF    EA6
C1    94F
C3    969
CA    9F1
D2    87F
D3    86C
DD    88D
DE    8B8
E7    B2F
E9    BCE
EB    BE8
F0    A53
F4    A1F
F7    A2A
FA    AFE

 

Sometime after you have posted all the data/codeword combinations (preferably all in increasing data order) I will start analyzing it. I don't know when I will be able to get to it, but if I can get the data by this weekend, then I can probably find time to play with it over the Thanksgiving holiday.

 

I just got the device back about an hour ago and have a little over half of the code words. I can provide those to you this evening if it helps. Otherwise, it will have to be Monday morning. Is that too late?

 

Nah, Monday will be fine. There's no point in me starting on them until I have them all.

Hopefully you aren't running them all as four-byte groups of identical data values. Instead, just use a single string of 256 data words that ramp from 0x00 to 0xFF. Or, use data runs of, say, 16 data values per run. Each run has a constant upper nibble and the lower nibble is ramped from 0x0 through 0xF. Then make 16 runs, each one with a different upper nibble.

 

Not running four byte groups, I just used that as an example to show that it repeats and that the FEC is interleaved between each byte. I ran eight of the 16 groups today (00-7F) and will run the remainder on Monday morning, at which time I will post the results.

 

Here are your list of codes. These all match the partial list that you posted except for 00, which you give as 55C and which I suspect is really 555.

If the codes below that are not in your partial list match your codes onces you fill in the gaps, it will be almost certain that 00 is supposed to be 555. Please measure it specifically and let me know what you see.

If this all works, then I can go into the encoding, decoding, and error correction algorithms that apply. I can also go into how I determined the correct value for 00 and tested it.

00 555
01 546
02 573
03 560
04 519
05 50A
06 53F
07 52C
08 5DE
09 5CD
0A 5F8
0B 5EB
0C 592
0D 581
0E 5B4
0F 5A7
10 450
11 443
12 476
13 465
14 41C
15 40F
16 43A
17 429
18 4DB
19 4C8
1A 4FD
1B 4EE
1C 497
1D 484
1E 4B1
1F 4A2
20 75F
21 74C
22 779
23 76A
24 713
25 700
26 735
27 726
28 7D4
29 7C7
2A 7F2
2B 7E1
2C 798
2D 78B
2E 7BE
2F 7AD
30 65A
31 649
32 67C
33 66F
34 616
35 605
36 630
37 623
38 6D1
39 6C2
3A 6F7
3B 6E4
3C 69D
3D 68E
3E 6BB
3F 6A8
40 152
41 141
42 174
43 167
44 11E
45 10D
46 138
47 12B
48 1D9
49 1CA
4A 1FF
4B 1EC
4C 195
4D 186
4E 1B3
4F 1A0
50 057
51 044
52 071
53 062
54 01B
55 008
56 03D
57 02E
58 0DC
59 0CF
5A 0FA
5B 0E9
5C 090
5D 083
5E 0B6
5F 0A5
60 358
61 34B
62 37E
63 36D
64 314
65 307
66 332
67 321
68 3D3
69 3C0
6A 3F5
6B 3E6
6C 39F
6D 38C
6E 3B9
6F 3AA
70 25D
71 24E
72 27B
73 268
74 211
75 202
76 237
77 224
78 2D6
79 2C5
7A 2F0
7B 2E3
7C 29A
7D 289
7E 2BC
7F 2AF
80 D5B
81 D48
82 D7D
83 D6E
84 D17
85 D04
86 D31
87 D22
88 DD0
89 DC3
8A DF6
8B DE5
8C D9C
8D D8F
8E DBA
8F DA9
90 C5E
91 C4D
92 C78
93 C6B
94 C12
95 C01
96 C34
97 C27
98 CD5
99 CC6
9A CF3
9B CE0
9C C99
9D C8A
9E CBF
9F CAC
A0 F51
A1 F42
A2 F77
A3 F64
A4 F1D
A5 F0E
A6 F3B
A7 F28
A8 FDA
A9 FC9
AA FFC
AB FEF
AC F96
AD F85
AE FB0
AF FA3
B0 E54
B1 E47
B2 E72
B3 E61
B4 E18
B5 E0B
B6 E3E
B7 E2D
B8 EDF
B9 ECC
BA EF9
BB EEA
BC E93
BD E80
BE EB5
BF EA6
C0 95C
C1 94F
C2 97A
C3 969
C4 910
C5 903
C6 936
C7 925
C8 9D7
C9 9C4
CA 9F1
CB 9E2
CC 99B
CD 988
CE 9BD
CF 9AE
D0 859
D1 84A
D2 87F
D3 86C
D4 815
D5 806
D6 833
D7 820
D8 8D2
D9 8C1
DA 8F4
DB 8E7
DC 89E
DD 88D
DE 8B8
DF 8AB
E0 B56
E1 B45
E2 B70
E3 B63
E4 B1A
E5 B09
E6 B3C
E7 B2F
E8 BDD
E9 BCE
EA BFB
EB BE8
EC B91
ED B82
EE BB7
EF BA4
F0 A53
F1 A40
F2 A75
F3 A66
F4 A1F
F5 A0C
F6 A39
F7 A2A
F8 AD8
F9 ACB
FA AFE
FB AED
FC A94
FD A87
FE AB2
FF AA1

 

55C was a typo. It is in fact 555. Here is the full list:

00    55    5
01    54    6
02    57    3
03    56    0
04    51    9
05    50    A
06    53    F
07    52    C
08    5D    E
09    5C    D
0A    5F    8
0B    5E    B
0C    59    2
0D    58    1
0E    5B    4
0F    5A    7
10    45    0
11    44    3
12    47    6
13    46    5
14    41    C
15    40    F
16    43    A
17    42    9
18    4D    B
19    4C    8
1A    4F    D
1B    4E    E
1C    49    7
1D    48    4
1E    4B    1
1F    4A    2
20    75    F
21    74    C
22    77    9
23    76    A
24    71    3
25    70    0
26    73    5
27    72    6
28    7D    4
29    7C    7
2A    7F    2
2B    7E    1
2C    79    8
2D    78    B
2E    7B    E
2F    7A    D
30    65    A
31    64    9
32    67    C
33    66    F
34    61    6
35    60    5
36    63    0
37    62    3
38    6D    1
39    6C    2
3A    6F    7
3B    6E    4
3C    69    D
3D    68    E
3E    6B    B
3F    6A    8
40    15    2
41    14    1
42    17    4
43    16    7
44    11    E
45    10    D
46    13    8
47    12    B
48    1D    9
49    1C    A
4A    1F    F
4B    1E    C
4C    19    5
4D    18    6
4E    1B    3
4F    1A    0
50    05    7
51    04    4
52    07    1
53    06    2
54    01    B
55    00    8
56    03    D
57    02    E
58    0D    C
59    0C    F
5A    0F    A
5B    0E    9
5C    09    0
5D    08    3
5E    0B    6
5F    0A    5
60    35    8
61    34    B
62    37    E
63    36    D
64    31    4
65    30    7
66    33    2
67    32    1
68    3D    3
69    3C    0
6A    3F    5
6B    3E    6
6C    39    F
6D    38    C
6E    3B    9
6F    3A    A
70    25    D
71    24    E
72    27    B
73    26    8
74    21    1
75    20    2
76    23    7
77    22    4
78    2D    6
79    2C    5
7A    2F    0
7B    2E    3
7C    29    A
7D    28    9
7E    2B    C
7F    2A    F
80    D5    B
81    D4    8
82    D7    D
83    D6    E
84    D1    7
85    D0    4
86    D3    1
87    D2    2
88    DD    0
89    DC    3
8A    DF    6
8B    DE    5
8C    D9    C
8D    D8    F
8E    DB    A
8F    DA    9
90    C5    E
91    C4    D
92    C7    8
93    C6    B
94    C1    2
95    C0    1
96    C3    4
97    C2    7
98    CD    5
99    CC    6
9A    CF    3
9B    CE    0
9C    C9    9
9D    C8    A
9E    CB    F
9F    CA    C
A0    F5    1
A1    F4    2
A2    F7    7
A3    F6    4
A4    F1    D
A5    F0    E
A6    F3    B
A7    F2    8
A8    FD    A
A9    FC    9
AA    FF    C
AB    FE    F
AC    F9    6
AD    F8    5
AE    FB    0
AF    FA    3
B0    E5    4
B1    E4    7
B2    E7    2
B3    E6    1
B4    E1    8
B5    E0    B
B6    E3    E
B7    E2    D
B8    ED    F
B9    EC    C
BA    EF    9
BB    EE    A
BC    E9    3
BD    E8    0
BE    EB    5
BF    EA    6
C0    95    C
C1    94    F
C2    97    A
C3    96    9
C4    91    0
C5    90    3
C6    93    6
C7    92    5
C8    9D    7
C9    9C    4
CA    9F    1
CB    9E    2
CC    99    B
CD    98    8
CE    9B    D
CF    9A    E
D0    85    9
D1    84    A
D2    87    F
D3    86    C
D4    81    5
D5    80    6
D6    83    3
D7    82    0
D8    8D    2
D9    8C    1
DA    8F    4
DB    8E    7
DC    89    E
DD    88    D
DE    8B    8
DF    8A    B
E0    B5    6
E1    B4    5
E2    B7    0
E3    B6    3
E4    B1    A
E5    B0    9
E6    B3    C
E7    B2    F
E8    BD    0
E9    BC    E
EA    BF    B
EB    BE    8
EC    B9    1
ED    B8    2
EE    BB    7
EF    BA    4
F0    A5    3
F1    A4    0
F2    A7    5
F3    A6    6
F4    A1    F
F5    A0    C
F6    A3    9
F7    A2    A
F8    AD    8
F9    AC    B
FA    AF    E
FB    AE    D
FC    A9    4
FD    A8    7
FE    AB    2
FF    AA    1

 

Aaarrrgghhh!!

Why did you change the format of your data? I wrote my analyzer to read your prior format and now you went and changed it so I had to update my analyzer so that it can read the new one.

Please check your value for data E8. You have BD0 and I have BDD. Other than that, all of your codes agree with the ones I generated.

Glad to hear that 00 was a typo and is really 555.

When I have some time (which should happen over the Thanksgiving break), I'll walk through how I analyzed the data. Perhaps it might even make a good blog post.

 

Yes, it should be BDD. Sorry. Do you need me to re-post the data in the original format? Can you give me a hint as to how you got your list? The suspense is killing me. The other piece to the puzzle is the length period which comes immediately before the data field. Seven bytes transmitted: Length period = 450, Eight bytes: 5DE, Nine bytes: 7D4. I can get more if needed.