Forums

Viterbi decoding of Repetition codes. Is it possible?

Started by Communications_engineer March 14, 2009
Hello, now my question is that can we do viterbi decoding of a
repetition code; for eg, I have an input '1' so I repeat it 20 times
(I know this not good as an error correction code and also as far as
efficient use of channel capacity is concerned, but I want to know
this for knowledge) and vice versa for '0'

So for a sequence 1 0 1 1 0 moving right to left (in order)

I get

1111111111111111111100000000000000000000111111111111111111111111111111111111111100000000000000000000


now after the channel corrupts bits



1111000001110101010101011111111000000001111111100000011111111111100000001111110000000000110000000000


So how can I make viterbi algo decode it? How can I create a Trellis
for this?
On 14 Mrz., 16:23, Communications_engineer
<communications_engin...@yahoo.com> wrote:
> Hello, now my question is that can we do viterbi decoding of a > repetition code; for eg, I have an input '1' so I repeat it 20 times > (I know this not good as an error correction code and also as far as > efficient use of channel capacity is concerned, but I want to know > this for knowledge) and vice versa for '0' > > So for a sequence 1 0 1 1 0 moving right to left (in order) > > I get > > 1111111111111111111100000000000000000000111111111111111111111111111111111111111100000000000000000000 > > now after the channel corrupts bits > > 1111000001110101010101011111111000000001111111100000011111111111100000001111110000000000110000000000 > > So how can I make viterbi algo decode it? How can I create a Trellis > for this?
You don't need the Viterbi algorithm here because the symbles are encoded *independently* in your case. It can't get any better than simply counting the number of zeros and ones in a 20-bit block and selecting the majority. The Viterbi algorithm can help you find state transitions. But you don't have any state transitions. Cheers! SG
On Mar 14, 8:42&#2013266080;pm, SG <s.gesem...@gmail.com> wrote:
> On 14 Mrz., 16:23,Communications_engineer > > > > > > > > <communications_engin...@yahoo.com> wrote: > > Hello, now my question is that can we do viterbi decoding of a > > repetition code; for eg, I have an input '1' so I repeat it 20 times > > (I know this not good as an error correction code and also as far as > > efficient use of channel capacity is concerned, but I want to know > > this for knowledge) and vice versa for '0' > > > So for a sequence 1 0 1 1 0 moving right to left (in order) > > > I get > > > 1111111111111111111100000000000000000000111111111111111111111111111111111111111100000000000000000000 > > > now after the channel corrupts bits > > > 1111000001110101010101011111111000000001111111100000011111111111100000001111110000000000110000000000 > > > So how can I make viterbi algo decode it? How can I create a Trellis > > for this? > > You don't need the Viterbi algorithm here because the symbles are > encoded *independently* in your case. &#2013266080;It can't get any better than > simply counting the number of zeros and ones in a 20-bit block and > selecting the majority. &#2013266080;The Viterbi algorithm can help you find state > transitions. &#2013266080;But you don't have any state transitions. > > Cheers! > SG
Alright, lets have state transitions. Lets say I represent my; '1' as 10101010101010101010 and '0' as 01010101010101010101 for my encoded sequence for 1 0 1 1 0 will be 10101010101010101010 0101010101010101010110101010101010101010 10101010101010101010 01010101010101010101 and now I get the same error sequence as before. Can I now use Viterbi? Also, if I can represent this coding procedure by a state diagram, I can use viterbi, right? Secondly, now that I have state transitions would viterbi yield me better results, better than simple repetition codes, I know it would not be optimal
On Mar 15, 3:36&#2013266080;am, Communications_engineer
<communications_engin...@yahoo.com> wrote:
> On Mar 14, 8:42&#2013266080;pm, SG <s.gesem...@gmail.com> wrote: > > > > > On 14 Mrz., 16:23,Communications_engineer > > > <communications_engin...@yahoo.com> wrote: > > > Hello, now my question is that can we do viterbi decoding of a > > > repetition code; for eg, I have an input '1' so I repeat it 20 times > > > (I know this not good as an error correction code and also as far as > > > efficient use of channel capacity is concerned, but I want to know > > > this for knowledge) and vice versa for '0' > > > > So for a sequence 1 0 1 1 0 moving right to left (in order) > > > > I get > > > > 1111111111111111111100000000000000000000111111111111111111111111111111111111111100000000000000000000 > > > > now after the channel corrupts bits > > > > 1111000001110101010101011111111000000001111111100000011111111111100000001111110000000000110000000000 > > > > So how can I make viterbi algo decode it? How can I create a Trellis > > > for this? > > > You don't need the Viterbi algorithm here because the symbles are > > encoded *independently* in your case. &#2013266080;It can't get any better than > > simply counting the number of zeros and ones in a 20-bit block and > > selecting the majority. &#2013266080;The Viterbi algorithm can help you find state > > transitions. &#2013266080;But you don't have any state transitions. > > > Cheers! > > SG > > Alright, lets have state transitions. Lets say I represent my; > > &#2013266080;'1' as 10101010101010101010 > &#2013266080;and > > '0' as 01010101010101010101 > > for my encoded sequence for 1 0 1 1 0 will be > 10101010101010101010 0101010101010101010110101010101010101010 > 10101010101010101010 01010101010101010101 > > and now I get the same error sequence as before. Can I now use > Viterbi? Also, if I can represent this coding procedure by a state > diagram, I can use viterbi, right?
Um. Your state transitions are really really trivial. Nobody's saying that you cannot use Viterbi to decode your code. In fact, in general any linear code can be decoded using Viterbi by writing it into a (possibly time-varying) trellis form.
> > Secondly, now that I have state transitions would viterbi yield me > better results, better than simple repetition codes, I know it would > not be optimal
You'll get the same answer. All you did was basically to scramble your code with the sequence (-1)^n. Viterbi decoding is a technique for maximum-likelihood sequence estimation. If you already have another, much simpler maximum- likelihood decoder, then the performance should be the same, by definition. Julius
On 15 Mrz., 08:36, Communications_engineer
<communications_engin...@yahoo.com> wrote:
> On Mar 14, 8:42&#2013266080;pm, SG <s.gesem...@gmail.com> wrote: > > [...] You don't need the Viterbi algorithm here because the symbels > > are encoded *independently* in your case. [...] > > Alright, lets have state transitions. Lets say I represent my; > > &#2013266080;'1' as 10101010101010101010 > &#2013266080;and > > '0' as 01010101010101010101
No, by "state transition" I meant something different. In your case you only have one state. In this one state the input of "0" is mapped to the output of "01010101010101010101" and the input of "1" is mapped to the output of "10101010101010101010". This mapping doesn't change. So, each 20 bit block can be decoded independently. You don't gain anything by using the Viterbi algorithm. But if you have more "states" and a mapping that depends on the state and the state changes somehow depending on the to-be-coded bit, the Viterbi algorithm can find the most likely sequence of states which also gives you the most likely input to the encoder. (Example: Convolutional codes) Cheers! SG
On Mar 15, 4:12&#2013266080;pm, SG <s.gesem...@gmail.com> wrote:
> On 15 Mrz., 08:36, Communications_engineer > > <communications_engin...@yahoo.com> wrote: > > On Mar 14, 8:42&#2013266080;pm, SG <s.gesem...@gmail.com> wrote: > > > [...] You don't need the Viterbi algorithm here because the symbels > > > are encoded *independently* in your case. [...] > > > Alright, lets have state transitions. Lets say I represent my; > > > &#2013266080;'1' as 10101010101010101010 > > &#2013266080;and > > > '0' as 01010101010101010101 > > No, by "state transition" I meant something different. In your case > you only have one state. In this one state the input of "0" is mapped > to the output of "01010101010101010101" and the input of "1" is mapped > to the output of "10101010101010101010". This mapping doesn't change. > So, each 20 bit block can be decoded independently. &#2013266080;You don't gain > anything by using the Viterbi algorithm. > > But if you have more "states" and a mapping that depends on the state > and the state changes somehow depending on the to-be-coded bit, the > Viterbi algorithm can find the most likely sequence of states which > also gives you the most likely input to the encoder. > > (Example: Convolutional codes) > > Cheers! > SG
Understood, Julius and SG. Thank you much indeed Now, let us have states If I now have 00 then my output is 01010101010101010101 01010101010101010101 01 01010101010101010101 10101010101010101010 10 10101010101010101010 01010101010101010101 11 10101010101010101010 10101010101010101010 I'm sorry if I'm getting on your nerves :) But over here I have 4 states, right? 00, 01, 10, 11 with these outputs. As you can see the ouputs are similar to what I had with repetition codes. Now would this have any better performance than my repetition codes?
On 15 Mrz., 15:04, Communications_engineer
<communications_engin...@yahoo.com> wrote:
> On Mar 15, 4:12&#2013266080;pm, SG <s.gesem...@gmail.com> wrote: > > No, by "state transition" I meant something different. In your case > > you only have one state. In this one state the input of "0" is mapped > > to the output of "01010101010101010101" and the input of "1" is mapped > > to the output of "10101010101010101010". This mapping doesn't change. > > So, each 20 bit block can be decoded independently. &#2013266080;You don't gain > > anything by using the Viterbi algorithm. > > > But if you have more "states" and a mapping that depends on the state > > and the state changes somehow depending on the to-be-coded bit, the > > Viterbi algorithm can find the most likely sequence of states which > > also gives you the most likely input to the encoder. > > Understood, Julius and SG. Thank you much indeed > > Now, let us have states > > If I now have 00 then my output is 01010101010101010101 > 01010101010101010101 > &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080;01 &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; 01010101010101010101 > 10101010101010101010 > &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080;10 &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; 10101010101010101010 > 01010101010101010101 > &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080;11 &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; 10101010101010101010 > 10101010101010101010 > > I'm sorry if I'm getting on your nerves :)
I don't think you understood. Actually, you didn't change anything. You still map 0 -> 01010101010101010101 1 -> 10101010101010101010 only that you just combined two blocks into one for no reason. Your encoder has no state simply because there's no need to remember the last bits to encode the next bits. It's all done independently. This how I would describe your example with a table: state | input | output | resulting state ------+-------+--------+---------------- S0 | 0 | 010101 | S0 S0 | 1 | 101010 | S0 It means your when your encoder is in state S0 and the input is "0" the output is "010101" and the resulting state is S0, etc To do something more advanved you would introduce other states like this: state | input | output | resulting state ------+-------+--------+---------------- S0 | 0 | ??? | S0 S0 | 1 | ??? | S1 S1 | 0 | ??? | S2 S1 | 1 | ??? | S3 S2 | 0 | ??? | S3 S2 | 1 | ??? | S2 S3 | 0 | ??? | S1 S3 | 1 | ??? | S0 where each "???" corresponds to some "output code words" you have to choose (for every occurence of course). This is a code with 4 states that are connected in a (standard) way so that a change of a single input bit can affect all following output code words. You can picture this table as a graph with 4 nodes and an edge for each entry that connects two states and has a label "input=x, output=y". The art is choosing the state transitions and outputs. Read more: - Convolutional Codes - Turbo Codes - Hidden Markov Modell There are some slight differences in terms of modelling. The standard Hidden Markov Model doesn't assign the output to edges but to its states which would double the number of states in your case. Cheers! SG
On 15 Mrz., 15:04, Communications_engineer
<communications_engin...@yahoo.com> wrote:
> Now, let us have states > > If I now have 00 then my output is 01010101010101010101 > 01010101010101010101 > &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080;01 &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; 01010101010101010101 > 10101010101010101010 > &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080;10 &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; 10101010101010101010 > 01010101010101010101 > &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080;11 &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; 10101010101010101010 > 10101010101010101010
What you're trying to do looks like "block codes". You certainly can combine multiple input bits to a block and assign all possible variations some unique output code word: input output ------------ 00 0111010000010110 01 0001110010010000 10 1010011100111111 11 0100111110010111 (just an example, randomly chosen output bits) This is better than coding 1-bit blocks or your approach of 2-bit- block coding. Still, you can decode blocks *independently* and don't require the Viterbi algoritm. Cheers! SG
On Sun, 15 Mar 2009 07:04:58 -0700 (PDT), Communications_engineer
<communications_engineer@yahoo.com> wrote:

>On Mar 15, 4:12&#2013266080;pm, SG <s.gesem...@gmail.com> wrote: >> On 15 Mrz., 08:36, Communications_engineer >> >> <communications_engin...@yahoo.com> wrote: >> > On Mar 14, 8:42&#2013266080;pm, SG <s.gesem...@gmail.com> wrote: >> > > [...] You don't need the Viterbi algorithm here because the symbels >> > > are encoded *independently* in your case. [...] >> >> > Alright, lets have state transitions. Lets say I represent my; >> >> > &#2013266080;'1' as 10101010101010101010 >> > &#2013266080;and >> >> > '0' as 01010101010101010101 >> >> No, by "state transition" I meant something different. In your case >> you only have one state. In this one state the input of "0" is mapped >> to the output of "01010101010101010101" and the input of "1" is mapped >> to the output of "10101010101010101010". This mapping doesn't change. >> So, each 20 bit block can be decoded independently. &#2013266080;You don't gain >> anything by using the Viterbi algorithm. >> >> But if you have more "states" and a mapping that depends on the state >> and the state changes somehow depending on the to-be-coded bit, the >> Viterbi algorithm can find the most likely sequence of states which >> also gives you the most likely input to the encoder. >> >> (Example: Convolutional codes) >> >> Cheers! >> SG > >Understood, Julius and SG. Thank you much indeed > >Now, let us have states > >If I now have 00 then my output is 01010101010101010101 >01010101010101010101 > 01 01010101010101010101 >10101010101010101010 > 10 10101010101010101010 >01010101010101010101 > 11 10101010101010101010 >10101010101010101010 > >I'm sorry if I'm getting on your nerves :) > >But over here I have 4 states, right? 00, 01, 10, 11 with these >outputs. As you can see the ouputs are similar to what I had with >repetition codes. Now would this have any better performance than my >repetition codes?
I'll add a little to what's been said. Hopefully it'll help. In order to add state transitions you really need to add some memory to the encoder. For convolutional codes, which are typically what Viterbi decoders are used to decode, this is expressed as k, the "constraint length". Another thing that typically happens with codes that have error correcting capability is that "overhead" or "parity" gets added to the stream so that there are bits transmitted than information bits. This is what provides the redundancy that a decoder can exploit to correct errors. Your code has neither memory nor overhead (i.e., the code rate is 1 and k=0). You do have two states, one and zero, but as Julius said that's pretty trivial and is indistinguishable from the information states. So, adding a code with states will also add memory since it'll be necessary to track the state transitions, and it'll also add overhead so more bits will come out of the encoder than went in. You might want to do some research on Convolutional Codes and how Viterbi decoders are used to decode them. I suspect you'll see quickly what you've been missing. Eric Jacobsen Minister of Algorithms Abineau Communications http://www.ericjacobsen.org Blog: http://www.dsprelated.com/blogs-1/hf/Eric_Jacobsen.php
On Mar 16, 2:32&#2013266080;am, Eric Jacobsen <eric.jacob...@ieee.org> wrote:
> On Sun, 15 Mar 2009 07:04:58 -0700 (PDT), Communications_engineer > > > > > > <communications_engin...@yahoo.com> wrote: > >On Mar 15, 4:12&#2013266080;pm, SG <s.gesem...@gmail.com> wrote: > >> On 15 Mrz., 08:36, Communications_engineer > > >> <communications_engin...@yahoo.com> wrote: > >> > On Mar 14, 8:42&#2013266080;pm, SG <s.gesem...@gmail.com> wrote: > >> > > [...] You don't need the Viterbi algorithm here because the symbels > >> > > are encoded *independently* in your case. [...] > > >> > Alright, lets have state transitions. Lets say I represent my; > > >> > &#2013266080;'1' as 10101010101010101010 > >> > &#2013266080;and > > >> > '0' as 01010101010101010101 > > >> No, by "state transition" I meant something different. In your case > >> you only have one state. In this one state the input of "0" is mapped > >> to the output of "01010101010101010101" and the input of "1" is mapped > >> to the output of "10101010101010101010". This mapping doesn't change. > >> So, each 20 bit block can be decoded independently. &#2013266080;You don't gain > >> anything by using the Viterbi algorithm. > > >> But if you have more "states" and a mapping that depends on the state > >> and the state changes somehow depending on the to-be-coded bit, the > >> Viterbi algorithm can find the most likely sequence of states which > >> also gives you the most likely input to the encoder. > > >> (Example: Convolutional codes) > > >> Cheers! > >> SG > > >Understood, Julius and SG. Thank you much indeed > > >Now, let us have states > > >If I now have 00 then my output is 01010101010101010101 > >01010101010101010101 > > &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; 01 &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; 01010101010101010101 > >10101010101010101010 > > &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; 10 &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; 10101010101010101010 > >01010101010101010101 > > &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; 11 &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080; 10101010101010101010 > >10101010101010101010 > > >I'm sorry if I'm getting on your nerves :) > > >But over here I have 4 states, right? 00, 01, 10, 11 with these > >outputs. As you can see the ouputs are similar to what I had with > >repetition codes. Now would this have any better performance than my > >repetition codes? > > I'll add a little to what's been said. &#2013266080; Hopefully it'll help. > > In order to add state transitions you really need to add some memory > to the encoder. &#2013266080; For convolutional codes, which are typically what > Viterbi decoders are used to decode, this is expressed as k, the > "constraint length". &#2013266080;Another thing that typically happens with codes > that have error correcting capability is that "overhead" or "parity" > gets added to the stream so that there are bits transmitted than > information bits. &#2013266080; This is what provides the redundancy that a > decoder can exploit to correct errors. > > Your code has neither memory nor overhead (i.e., the code rate is 1 > and k=0). &#2013266080;You do have two states, one and zero, but as Julius said > that's pretty trivial and is indistinguishable from the information > states. > > So, adding a code with states will also add memory since it'll be > necessary to track the state transitions, and it'll also add overhead > so more bits will come out of the encoder than went in. > > You might want to do some research on Convolutional Codes and how > Viterbi decoders are used to decode them. &#2013266080; I suspect you'll see > quickly what you've been missing. > > Eric Jacobsen > Minister of Algorithms > Abineau Communicationshttp://www.ericjacobsen.org > > Blog:http://www.dsprelated.com/blogs-1/hf/Eric_Jacobsen.php- Hide quoted text - > > - Show quoted text -
Thanks guys. I do have decent information about Convolutional codes and Viterbi algorithm for its decoding. But I was slightly confused on whether I could use Viterbi for repetition codes or not, even though they are not efficient. Appreciate your help. Cheers to all!