Viterbi Encoder

[tex23bm]

Hey, I'm looking for resources on a Viterbi Encoder.

I can't find any kind of a good explanation dumbed down to my level. I'm not going to lie, i like my explanations of algorithms as stupid as possible.

tex23bm

[tex23bm]

basically i figured it out. There's really no such thing as a viterbi encoder, viterbi is more a method of decoding. the convolution encoding and viterbi decoding algorithms can be found on this site, i found it most helpful.


http://home.netcom.com/~chip.f/viterbi/algrthms.html

but thanks guys for hel..... wait a second you guys proved useless.

bill

[tex23bm]

Alright, I see that people are still reading the thread. So I'm going to give you kids a little update.

I am almost finished with the Viterbi Decoder. I used Convolution encoding. When I am finihsed I will post the source code, and whatever report/explanation i write up on my site.

tex23bm

[yiannakop]

Interesting. But I believe you should post in the Algorithms section.
Regards,
Theodore

[tex23bm]

oh, wow.

Thanks, I'm actually quite new to this site. Didn't even realize there was a section for that.

tex23bm

[tex23bm]

Boom.

Alright Kids. Here's the Deal: I got the encoder working and I got the decoder working.

I arbitrarilly decided to expand 7 bit chunks of data into 18 bit pieces of data. This was 1:2 expansion with 4 bits of flushing data. (roughly 1:2.57).

I then saved this expansion to a file.

I grabbed the data from that file and ran the decoding function. needless to say my code has a number of bugs. And i do mean a number.

I decided on keeping my file to 7 byte chunks and then expanding that to 18 bytes. My expansion worked to perfection. I looked at all the bits in my example and they were awesome. Then when I brought them back from the file. well out of 144 bits 143 were correct. bit number 130 (index 129) was wrong. Don't ask me why, don't ask me how, it just was.

I thought about solving this, but then i remembered, hey if this is error correction it WILL be able to handle 1 wrong bit for 143 right ones. I moved on.

Then Oh EM Eff gee my program decided to write over the last 18 bits of the file. everything else was gravy, but the last 18 bits were screwed up. I don't know if i was overstepping the bounds of the array, but i output the bits. They were awesome. I ran the function and they were screwed. I ended up making a spare copy of the last 18 bits and using that. I know this was the lazy way out. Anywho, the short version is, I have it working if you want a copy of the code e-mail me, my code should be on my site in the next couple of days. provided i'm not too lazy.

tex23bm

[tex23bm]

So, I have finished with the encoder and decoder. I'm a little dissappointed in the abilities of the decoder. Here's the problem that i kept hitting with it.

When I had two paths that produced the same amount of error the decoder couldn't resonably decide which one to choose. Now you might make the mistake of saying that the path doesn't matter, however if this path that mergers happens to be the path with the least error you're screwed. You can't tell if you have say 2 1 bit errors or 1 2 bit error. My solution for this was a very simple checksum function. after running several tests on my code I came to the realization that something like 10% of the decoding attempts had this catastrophic error problem and that when it had to run again more than one time it usually took thousands of iterations to work. This indicates a larger problem with My code than the algorithm. I'm not really worried though because i got it to work.

unfortunately bit 130 is still screwed, poor little guy.

also important to note is that my code handles filesizes divisible by 7. if your file is not divisible by seven, well you get the rest of the file to repeat.
EX:
12345678
|
V
12345678234567
not a good thing, but I did get you the working code. So don't sweat the small stuff.

I will try to comment my code before i post it on my site.
I will be typing up a nice report much like i did for DES encryption.
any questions or comments feel free to post or PM or Email.

tex23bm