FEC code explanation -Convolutional Encoder for encoding data bits

Thread Starter

JimmyCho

Joined Aug 1, 2020
44
Hi guys!
Im trying to built as software a block that's called Convolutional Encoder that its input is data bits -I attached down a photo for it-
I really read here deeply about -FEC- Convolutional Encoder: https://www.ti.com/lit/an/swra642/swra642.pdf
And I didn't understand how it works, what's its mode of operation and what's outputting? I really confused about it FEC -Convolutional Encoder.
Could anyone please explain it to me by an example of data bit like if I enter to it "010101" so what its output?! and how it works? specifically the concept/scheme of FEC isn't understandable for me!

thanks alot for any explanation.
2.JPG



1.jpg
 
Last edited:

Papabravo

Joined Feb 24, 2006
14,393
The purpose of FEC (Forward Error Correction) is to introduce enough redundancy into a message so that a limited number of errors, occurring anywhere in the message, can be corrected. This is often desirable when the cost of a retransmission is high or impossible because there is no reverse channel to send a retransmission request. The cost for this redundancy to correct errors is the requirement for greater bandwidth for the transmission. The method for implementation will be a feedback shift register. with XOR gates. similar to the ones used for computing a CRC (Cyclic Redundancy Check). They can also be used with ECC (Error Correcting Codes).

Once again you need to find a mentor you can discuss these issues with.

Have you purchased your personal copy of:
Bernard Sklar, Digital Communications – Fundamentals and Applications, 2nd Edition.
https://www.amazon.com/DIGITAL-COMMUNICATIONS-2ED-Bernard-Sklar-dp-8131720926/dp/8131720926/ref=mt_other?_encoding=UTF8&me=&qid=1598050448


Looks like a bargain at $50

If not, what is stopping you?
How are you going to figure it out if you try to do this on the cheap?
 
Last edited:

Thread Starter

JimmyCho

Joined Aug 1, 2020
44
The purpose of FEC (Forward Error Correction) is to introduce enough redundancy into a message so that a limited number of errors, occurring anywhere in the message, can be corrected. This is often desirable when the cost of a retransmission is high or impossible because there is no reverse channel to send a retransmission request. The cost for this redundancy to correct errors is the requirement for greater bandwidth for the transmission. The method for implementation will be a feedback shift register. with XOR gates. similar to the ones used for computing a CRC (Cyclic Redundancy Check). They can also be used with ECC (Error Correcting Codes).

Once again you need to find a mentor you can discuss these issues with.

Have you purchased your personal copy of:
Bernard Sklar, Digital Communications – Fundamentals and Applications, 2nd Edition.
https://www.amazon.com/DIGITAL-COMMUNICATIONS-2ED-Bernard-Sklar-dp-8131720926/dp/8131720926/ref=mt_other?_encoding=UTF8&me=&qid=1598050448


Looks like a bargain at $50

If not, what is stopping you?
How are you going to figure it out if you try to do this on the cheap?
Hi ! I will manage myself to buy it but because I have just 4days to implement the FEC encoder, could you assist me ? (not meaning to code it :) I mean to understand how it works, its mode operation by examples?)

really appreciated!
 

Papabravo

Joined Feb 24, 2006
14,393
The best I can do is explain what I think the diagram in the TI datasheet is trying to tell you.
Look at figure 3 on page 4.
  1. Each of the numbered boxes in Figure 3 is a D-Type Flip-Flop
  2. The D input is on the left side of the box, the Q output is on the right side of the box
  3. There are 7 total stages of the shift register
  4. The bits in the seven Flip-Flops advance to the next stage on the rising edge of a clock pulse
  5. The clock for the Flip-Flops is not shown
  6. The incoming data stream enters the encoder at the D-input of Flip-Flop #6
  7. There are two data streams that exit the encoder labeled a₀ and a₁
  8. Each of the black dots represents a 2-input XOR gate
  9. Now for each output of an XOR gate you can write an equation for it's output
Here's the rub.

The output of the encoder has no specified initial condition that I am aware of. It may be the case that running the preamble through it establishes the initial condition. I don't know if that is true or not and I have no way of checking or determining that. You are on your own with four days to go and without some help at your place of employment you don't seem to have much in the way of chances for success. I'm sorry about that, but it is out of my hands.

Do you even have so much as a correctly coded example? Even if you produce this implementation, how did you plan to verify its correctness?
No offense, but I think you are well and truly up against a wall.
 
Last edited:

Thread Starter

JimmyCho

Joined Aug 1, 2020
44
The best I can do is explain what I think the diagram in the TI datasheet is trying to tell you.
Look at figure 3 on page 4.
  1. Each of the numbered boxes in Figure 3 is a D-Type Flip-Flop
  2. The D input is on the left side of the box, the Q output is on the right side of the box
  3. There are 7 total stages of the shift register
  4. The bits in the seven Flip-Flops advance to the next stage on the rising edge of a clock pulse
  5. The clock for the Flip-Flops is not shown
  6. The incoming data stream enters the encoder at the D-input of Flip-Flop #6
  7. There are two data streams that exit the encoder labeled a₀ and a₁
  8. Each of the black dots represents a 2-input XOR gate
  9. Now for each output of an XOR gate you can write an equation for it's output
Here's the rub.

The output of the encoder has no specified initial condition that I am aware of. It may be the case that running the preamble through it establishes the initial condition. I don't know if that is true or not and I have no way of checking or determining that. You are on your own with four days to go and without some help at your place of employment you don't seem to have much in the way of chances for success. I'm sorry about that, but it is out of my hands.

Do you even have so much as a correctly coded example? Even if you produce this implementation, how did you plan to verify its correctness?
No offense, but I think you are well and truly up against a wall.
About examples for verification of my code correctness it's not a big issue, first I need to implement the code and then I will verify 100% that it works properly (ofcourse by trying whole examples possibilities)
I tried to understand how FEC encoder works by this photo below(from the link that I attached here in the thread):
5.JPG
I didn't understand anything at all, from the first arrow where there's above of it K=7 till a0,a0 flowchart blocks ..this thing -the whole flowchart in the photo above- explain how fec encoder works , could you please explain in detail how the flow of mode operation of fec encoder works (i,e how fec encoder according to its described blocks above)?


Appreciate your help!
 

Thread Starter

JimmyCho

Joined Aug 1, 2020
44
I did that in post #4. Did you forget to read it?
Hi no really read it but still confused (didn't understand it and Im really stuck - no time :) - )
the fec encoder should have a map table that map codewords from specific pattern to another -that's what I found in internet explanation- , but here I don't have any table could I follow in order to map my inputs to the fec encoder .. here's my problem

Maybe I didn't understand how fec encoder works, could you attach me an example (hexa byte example would be also good) ? thanks alot
 

Papabravo

Joined Feb 24, 2006
14,393
Sorry, I don't have any examples that I know to be correct. I also have no information on establishing the initial conditions. Buy me a copy of Sklar, and I might be able to work it out.
 

andrewmm

Joined Feb 25, 2011
572
Ok, you are going to have fun with this,

as has already been shown, FEC's are one of many ways of adding redundancy / extra codes to a stream of data such that errors can be detected and corrected.

Lets try to get a common start point,
what other codes do you know about to do that sort of thing .
can you explain what a parity bit is and how it works ?
 

Papabravo

Joined Feb 24, 2006
14,393
Sorry, I don't have any examples that I know to be correct. I also have no information on establishing the initial conditions. Buy me a copy of Sklar, and I might be able to work it out.
I must be getting soft in the head. I have been meaning to try a digital circuit in LTspice since I downloaded the "Large" library from @Bordodynov Now, I don't have much practice with digital simulations in LTspice and I was definitely not concerned about setup and hold times and I did observe the flip-Flop outputs glitching. I decided to give you the circuit in case it helps you understand what is going on. I apologize for any mistakes I may have made. In this life there are simply NO guarantees.

FEC_Encoder.png
 

Attachments

Thread Starter

JimmyCho

Joined Aug 1, 2020
44
Ok, you are going to have fun with this,

as has already been shown, FEC's are one of many ways of adding redundancy / extra codes to a stream of data such that errors can be detected and corrected.

Lets try to get a common start point,
what other codes do you know about to do that sort of thing .
can you explain what a parity bit is and how it works ?
Im trying to build fec encoder by c or c++ language programming, so didn't get you what you're talking about..
 

Thread Starter

JimmyCho

Joined Aug 1, 2020
44
I must be getting soft in the head. I have been meaning to try a digital circuit in LTspice since I downloaded the "Large" library from @Bordodynov Now, I don't have much practice with digital simulations in LTspice and I was definitely not concerned about setup and hold times and I did observe the flip-Flop outputs glitching. I decided to give you the circuit in case it helps you understand what is going on. I apologize for any mistakes I may have made. In this life there are simply NO guarantees.

View attachment 215424
I really appreciate your effort, Im trying to coce my fec encoder by c or c++ software languages and not hardware as what you did, what you've done is still confusing me is how can I convert the concept of shift registers/xors to software language like c/c++.
here's my problem!

I really appreciate what you're attaching about hardware implementation..but unfortunately I need to program fec encoder in c/c++ language and it's hard for me to move from hardware implementation(what you attached ) to c/c++ programming code for fec encoder
 

Papabravo

Joined Feb 24, 2006
14,393
Right -- I understand. In order to write that program you need to understand whar the hardware is doing. If you can't do that then there is ZERO chance that you will EVEER write a program that will mimic the function of the hardware. Now it is way past time for you to buckle down and solve your problem one way or another. I had the same struggle 50 years ago as I was trying to figure out how to compute the CRC for writing to 9-Track Magnetic Tape. One more time; find somebody at your company who can help you, or take a couple of more months to figure it out on your own.

I was hoping a more explicit hardware diagram would be more helpful than the picture in the datasheet. Sadly you seem to be at sea. If I can answer any questions about the hardware please ask.
  1. The diagram shows 7 Flip-Flops arranged as a serial shift register
  2. Data enters the shift register on the left hand side at the "D" input
  3. The 8 gates all perform an Exclusive-OR function
  4. The voltage sources V1-V4 produce levels and pulses to control the CLR-BAR, D, PRESET, and CLK inputs for the Flip-Flops
  5. After A CLR-BAR pulse sets all Flip-Flops to "0" A data byte of 8 bits consisting of four "1"s and four "0"s is presented to the "D" of Flip-Flop Q0. LEAST SIGNIFICANT BIT FIRST.
  6. The Clock Generator produces 8 clock pulses to shift the data byte "0x0F" into the shift register
On a piece of paper record the values contained in each Flip-Flop and the output of each gate as you shift those 8 bits into the 7-bit shift register. That will give you the first example of mapping a byte of data (0x0F) to the outputs A₁ and A₀.

You may discover an algorithm that lets you do this in parallel one byte at a time; it is not guaranteed but possible. You could also buy a copy of Sklar and be done with it -- maybe. Your choice.
If you don't know how a "D" Flip-Flop and an Exclusive OR work, then you better quickly learn or you will continue to be at sea.
 
Last edited:

andrewmm

Joined Feb 25, 2011
572
Im trying to build fec encoder by c or c++ language programming, so didn't get you what you're talking about..
The language is in material,
what I'm asking is what experience do you have in these things ? then we can supply appropriate help.

As others have rightly said, talking to some one at your place is the best ,
as they will know what level of support you will need,

FEC's are just one of the many types of error detection / correction codes, once you have cracked one, then you can build on your knowledge.

hence my question,
as to what have you done before, asking about parity,

I would hope you knew about hamming distances, and running disparities

The fact you did not know about parity, which is the basis that FEC is built upon ,
is a worry.

I'm not confident I have the resources to guide you through building a FEC from this starting point,.
 

Thread Starter

JimmyCho

Joined Aug 1, 2020
44
Right -- I understand. In order to write that program you need to understand whar the hardware is doing. If you can't do that then there is ZERO chance that you will EVEER write a program that will mimic the function of the hardware. Now it is way past time for you to buckle down and solve your problem one way or another. I had the same struggle 50 years ago as I was trying to figure out how to compute the CRC for writing to 9-Track Magnetic Tape. One more time; find somebody at your company who can help you, or take a couple of more months to figure it out on your own.

I was hoping a more explicit hardware diagram would be more helpful than the picture in the datasheet. Sadly you seem to be at sea. If I can answer any questions about the hardware please ask.
  1. The diagram shows 7 Flip-Flops arranged as a serial shift register
  2. Data enters the shift register on the left hand side at the "D" input
  3. The 8 gates all perform an Exclusive-OR function
  4. The voltage sources V1-V4 produce levels and pulses to control the CLR-BAR, D, PRESET, and CLK inputs for the Flip-Flops
  5. After A CLR-BAR pulse sets all Flip-Flops to "0" A data byte of 8 bits consisting of four "1"s and four "0"s is presented to the "D" of Flip-Flop Q0. LEAST SIGNIFICANT BIT FIRST.
  6. The Clock Generator produces 8 clock pulses to shift the data byte "0x0F" into the shift register
On a piece of paper record the values contained in each Flip-Flop and the output of each gate as you shift those 8 bits into the 7-bit shift register. That will give you the first example of mapping a byte of data (0x0F) to the outputs A₁ and A₀.

You may discover an algorithm that lets you do this in parallel one byte at a time; it is not guaranteed but possible. You could also buy a copy of Sklar and be done with it -- maybe. Your choice.
If you don't know how a "D" Flip-Flop and an Exclusive OR work, then you better quickly learn or you will continue to be at sea.
I really appreciate your effort to help me, I will try my best to get help from my company members but because I have max one week to finish at least the understanding of the fec encoder that's why Im in a pressure and not having time and I know you're doing your best for me , appreciated ofcourse.

I've read about fec encoder on internet also, all its algorithms are using what's called "codeword" and according to it they encode the data, I understand the scheme of mapping before encoding to after encoding (output encoder), what's confusing me that I dont have the codeword in my case ( still not having the book so I guess the code word found on the book ..) , is there a way could I obtain the codeword of encoding in my fec encoder in my case? according to codeword I can easily understand and map the input data !

the codeword is a scheme that decide if the input to encoder is 0 then mapping it to 0011 for instance, if 1 then mapping it to 1100 ...so all depend on the codeword of my fec given encoder.
I found before three hours the book online finally!!!! it's here free online edition:
https://www.pdfdrive.com/digital-communication-fundamentals-and-application-e186245452.html
at page 381
-note that in my case as what the texas attached document said that our encoder is having K=7 .

Maybe by the hardware implementation code we decide the codeword of our fec encoder? I really didn't understand what's written there and if I was having time then I will more and more read it but sorry Im really stuck and need a boost with current time I have.

What I understand from the book, my fec encoder is work according to hamming distance we choose the minimum hamming distance across all possibilities and the corresponded pattern to the minimum is the output of the encoder..right?

appreciated for any effort
 
Last edited:

Thread Starter

JimmyCho

Joined Aug 1, 2020
44
Honestly by examples I learn more quickly so after attaching you the book, now we can move on to understand how fec encoder works? thanks alot
 

Papabravo

Joined Feb 24, 2006
14,393
I got the Kindle Version of Sklar for $11.90. I have not seen any references to "codeword" so I have no idea what you are referring to. Chapter 7 appears to be where the bulk of the relevant discussion takes place. They do identify the 1/2, K=7 encoder and I know a few more things.
  1. When you shift zeros into the encoder you clear it or flush it out.
  2. The XOR gates affect only the output, the data bits go through the seven stages of the shift register without modification and fall off the right hand edge.
  3. In operation there is no need for a RESET on the Flip-Flops because shifting 0's accomplishes the same function
  4. In your code it could never hurt to set the register to zero, even if you know it is already clear
A couple of other things are clear:
  1. In a program, you can operate the shift register and the XOR gates independently.
  2. The only external results that need to be visible are the outputs A₀ and A₁
The flow of your program should look like:
  1. Shift a data bit into the shift register
  2. Compute A₀ and A₁
Don't forget to shift some zeros into the register when you are done with the data.
That's it
 

Thread Starter

JimmyCho

Joined Aug 1, 2020
44
the code word that I'm meaning is shown in chapter 6 page 552 at the book that I linked it to you above(it's free download) , here it's:
1.jpg

Im now trying to understand what you wrote about the encoder k=7
 

andrewmm

Joined Feb 25, 2011
572
this is why I was asking about your understanding,
your in way to high ,

a code word in this context is just that, a code that represents the original code,
read the rest of that chapter to that point and you will get that,

your asking real simple questions, I'd strongly suggest, go away for a few days to a quiet place, read the book, understand it , and come back.
 

Thread Starter

JimmyCho

Joined Aug 1, 2020
44
this is why I was asking about your understanding,
your in way to high ,

a code word in this context is just that, a code that represents the original code,
read the rest of that chapter to that point and you will get that,

your asking real simple questions, I'd strongly suggest, go away for a few days to a quiet place, read the book, understand it , and come back.
but who said that I don't that that those codeword represent the orginal word? what I dont know is the codeword for encoder k=7!
 
Top