Reply by Communications_engineer●March 16, 20092009-03-16
On Mar 16, 2:32�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�pm, SG <s.gesem...@gmail.com> wrote:
> >> On 15 Mrz., 08:36, Communications_engineer
>
> >> <communications_engin...@yahoo.com> wrote:
> >> > On Mar 14, 8:42�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;
>
> >> > �'1' as 10101010101010101010
> >> > �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
>
> >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 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!
Reply by Eric Jacobsen●March 15, 20092009-03-15
On Sun, 15 Mar 2009 07:04:58 -0700 (PDT), Communications_engineer
<communications_engineer@yahoo.com> wrote:
>On Mar 15, 4:12�pm, SG <s.gesem...@gmail.com> wrote:
>> On 15 Mrz., 08:36, Communications_engineer
>>
>> <communications_engin...@yahoo.com> wrote:
>> > On Mar 14, 8:42�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;
>>
>> > �'1' as 10101010101010101010
>> > �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
>
>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
Reply by SG●March 15, 20092009-03-15
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
> � � � � � � � � � �01 � � � � � � � � � � � � � 01010101010101010101
> 10101010101010101010
> � � � � � � � � � �10 � � � � � � � � � � � � � 10101010101010101010
> 01010101010101010101
> � � � � � � � � � �11 � � � � � � � � � � � � � 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
Reply by SG●March 15, 20092009-03-15
On 15 Mrz., 15:04, Communications_engineer
<communications_engin...@yahoo.com> wrote:
> On Mar 15, 4:12�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. �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
> � � � � � � � � � �01 � � � � � � � � � � � � � 01010101010101010101
> 10101010101010101010
> � � � � � � � � � �10 � � � � � � � � � � � � � 10101010101010101010
> 01010101010101010101
> � � � � � � � � � �11 � � � � � � � � � � � � � 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
Reply by Communications_engineer●March 15, 20092009-03-15
On Mar 15, 4:12�pm, SG <s.gesem...@gmail.com> wrote:
> On 15 Mrz., 08:36, Communications_engineer
>
> <communications_engin...@yahoo.com> wrote:
> > On Mar 14, 8:42�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;
>
> > �'1' as 10101010101010101010
> > �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
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?
Reply by SG●March 15, 20092009-03-15
On 15 Mrz., 08:36, Communications_engineer
<communications_engin...@yahoo.com> wrote:
> On Mar 14, 8:42�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;
>
> �'1' as 10101010101010101010
> �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
Reply by julius●March 15, 20092009-03-15
On Mar 15, 3:36�am, Communications_engineer
<communications_engin...@yahoo.com> wrote:
> On Mar 14, 8:42�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. �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
>
> 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?
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
Reply by Communications_engineer●March 15, 20092009-03-15
On Mar 14, 8:42�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. �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
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
Reply by SG●March 14, 20092009-03-14
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
Reply by Communications_engineer●March 14, 20092009-03-14
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?