Friday, June 23, 2006

Hamming code: Error Correction Code

Something I spend 2 days re-learning from my MCA days!! Man am i forgetfull.. dont even know if my understanding is correct now..
Generating the Hamming code parity bits
First thing to understand about Hamming code is the following
Step1: Convert data into bits
D0, D1, D2…. Dn-1, Dn where n is divisable by 2
1 0 0 1 0 1 0 0
Step2: Next thing is called grouping.
Group Bits in sequence of powers of 2 – call them group index
[D0] [D1]…. [Dn] is grouped on power of 0 è[G0_0],[G0_1]…[G0_n]
[D0,D1] [D2, D3].. [Dn-1, Dn] is grouped on Power of 1 è[G1_0],[G1_1]…[G1_n]
[D0,D1, D2, D3].. [Dn-3, Dn-2,Dn-1, Dn] is grouped on Power of 2 è[G2_0],[G2_1]…[G2_n]
Max such groups possible is possible is n/2 è
[D0,.., Dn/2], [Dn/2+1,.., Dn] è[Gn/2_1][Gn/2_2]
Group index 0: [1], [0], [0], [1], [0], [1], [0], [0]
Group index 1: [1, 0], [0, 1], [0, 1], [0, 0]
Group index 2: [1, 0, 0, 1], [0, 1, 0, 0]

Step 3: Each Group has parity generated for all the data bits of each [Gx_y] using XOR.
[Gx_y] è Dy/x … XOR… D(y/x+1) XOR.. D(y/x+x)
Group Parity index 0: [1], [0], [0], [1], [0], [1], [0], [0] è same
Group Parity index 1: [1, 0], [0, 1], [0, 1], [0, 0] è [1], [1], [1], [0]
Group Parity index 2: [1, 0, 0, 1], [0, 1, 0, 0] è[0],[1]

Step 4: Parity Bits Pk and Pk’ are generated based on the following logic:
Where k is 0-n/2 -> same as a group index
Pk is the XOR of all Even parity bits of a group index generated in step 3.
Pk’ is the XOR of all ODD parity bits
So For Group Parity y,
[Gx_0] [Gx_1] [Gx_2] ..[Gx_y],
Pk = [Gx_0] XOR [Gx_2] [Gx_y-1]
Pk = [Gx_1] XOR [Gx_3] [Gx_y]
E.g :
G0 was: [1], [0], [0], [1], [0], [1], [0], [0]
P0: [1], XOR [0], XOR [0], XOR [0] è 1
P0’: [0],XOR, [1], XOR [1], XOR [0] è 0
G1 was : [1, 0], [0, 1], [0, 1], [0, 0] è [1], [1], [1], [0]
P1: [1, 0], XOR [0, 1] è [1], XOR [1]è 0
P1’: [0, 1], XOR [0, 0] è [1], XOR [0] è 1

G2 was: [1, 0, 0, 1], [0, 1, 0, 0] è[1],[1]
P2: [1, 0, 0, 1]è[0]
P2’: [0, 1, 0, 0] è[1]

Fixing a error:
Pold =Say we have old values for which the parity was computed (p0, p0’,p1, p1’ ,p2,p2’)
Pnew =new values generated out of the read values (pn0, pn0’,pn1, pn1’ ,pn2,pn2’)
The Pold XOR Pnew = X
If X==0, there is NO ECC error
If X == num_bits/2, the location of error is pointed by the place the error is. lest 3 bits shows which bit has the problem and rest of the same show where the byte where the problem is.
Else.. Bad data.. dump.. retry.

Friday, June 16, 2006

recipe for a code in schedule

am sleepy waiting for a t-con to happen that never seems to get finalized.. so here it goes.. From what i learnt (relearnt?) in the past couple of months: Why have my modules created least issues?
1. Be clear on what u need to do - fight with requirements teams if required. I love our requirement guys - they are good!
2. Estimate within reason - dont over budget/underbudget. But *spend time* on estimates - always be prepared for unexpected hardware/tools issues-estimate for it!! - I use a 3 point estimate as of now, till i get something better at least.
3. read a lot on the subject - TRMs, functional specs, similar implementation, irc logs, mailing list archives, other OS, validation code, what ever I can lay my hands on - the idea is know how the hardware works - thoroughly before touching s/w.
4. As a driver writer I need to know my users, so i talk to them.. in person, over emails, the final user is the best teacher.. (next to the requirements blokes). meetings.. over all architecture - usually i start along with architecture team.
5. spend time in proper design - much munching required before even touching rational rose/msword for documentation - very important if code is huge. Some of my techniques
a) walk up and down while visualizing what if scenarios - I am pretty restless unless i create a mental picture on what i think the code should behave in total - i love the concept of gears - each turning the other..
b) draw the ideas on a white board and paper.. lots of times, rub re-draw
c) create the final idea on paper with a marker/pen
d) go to s/w tools like rational rose and start depicting what i want - i love sequence diagrams
e) code me in - compile test it at the very least - no platform might be available now.
Pri-Silicon platforms Vs Silicon platforms!
Hmm.. Pri-Silicon platforms are the nearest things to the hardware on which my code will finally work on. Many manifestations exist - FPGA, s/w, previous Si with new boards and what not.. all try to emuate the hardware, but may miss the mark sometimes.. Despite how much ever i curse a Pre-Si platform - there is nothing like it to make my understanding of the hardware better and my code better probable on the actual hardware(when ever it comes)- I usually use Lauterbach on them and after a day or so, I get to know what it does altogether. I have spend months and months on PreSi platforms to bring code up in hours when the real hardware comes in.. but then.. I am a fortunate programmer!! Most blokes dont get that luxury. The *true* programmer is one who reads the data sheet, writes the code and the bloddy code runs the first time on the real hardware.. Now, that *is* awesome and I know a couple of blokes who fit that bill.. Dont blame me for hero worship.. they deserve it!! I am more of a write-test-fix-write-test loop
f) write real real real real mean test cases - always think as if it is ur enemy's code ur testing - u want to kill it and u know its weakness.. I call it Offensive Testing and Defensive Programming (okay I stole it from Defensive Driving over here ;) but then who cares as long as the cliche sticks)!!

6) lets see what else? yeah - coding style
a) I love simple code.. as much as i can make it - my mind works crooked for most part of my lifetime writing obfuscated nested macros that people hate me for.. but elegance is what i strive for.. if u can show me how my code can be better.. i love it..
b) Most importantly, i hate hacks.. if i see a problem, i want and will spend time to fix the root cause. hacks are recipies for more time spend debugging!
c) Always ask for review - for a person who thinks(or tries to think) faster than the speed he codes.. I end up making real basic mistakes.. and knowing that weakness.. I always ask for reviews. I know some breeds of programmers - the fast and sloppy (like me), the slow and thorough and the fast and thorough (RKW). I always like the thorough guys for review.. love them when they kick my butt. e.g. why is OMAP OSS Audio driver capable of handling only one Codec Chip? Dumb me... errr....stutter stutter... Embedded devices have only one codec...Reply -> so and so has two of them.. one for routing music (high sampling rates- 44.1/48khz or even 96khz), and other solely for voice (8/16khz mono) calls. aaaarggh... how dumb of me... it is too late now.. make it an enhancement -> next time i look at the code I will fix it.. Git... some day soon I shall come....
g) tricks:
i) I used to hate gotos... now i use them to improve my code.. yet.. i am careful..
ii) i learnt a new thing.. how to handle multiple checks? OR each check to a variable and test it in one shot - cleaner code that Lindent does not kill- though the optimizer will put the same instructions..
h) Avoid the "i will fix it loop" - many problems have been though over by others and fixed by others.. it never hurts to ask.. my rule of thumb.. if it is logic and i could not fix in 2 days.. i am gonna holler..HELPPPPP...
i) Wish I can overcome this - "I am a super programmer syndrome" - when lesser people start commenting usefully on ur code.. the "I am invincible"(a.k.a 007 GoldenEye) syndrome creeps in.. too bad..

7) Oh yeah - the golden rule (my favorite and one that makes me infamous) - all ways be prepared to re-factor. I use platform changes as opportunity to re-visit code (even that which is written by me) to create a nice rewrite (which basically means do all from step 1 onwards).. and i try never to hack in code on top of what was previously present (i dont deny that i have done it.. but I try as far as possible not to).

8) Love the process and be prepared to bend the rules sometimes.. like writing design documents after code.. but keep the spirit.. never write code without a design.. design need not mean design documents.. they need to be somewhere - simple ones : pictures in mind; complex ones: rational rose/ paper. later on i update those designs and put them in a document when my code is done and ready to go in for review... but usually i end up doing this before testing.. so Some times.. DD is something i visit every 6 months or so.. looking at some of my DD's histories. - Remember the rule - Process is all guidelines - the main thing is absorbing the essense of it.. not necessarily following it verbatim..

I am sure lots of programmers out there have better inputs than I have, but these are what I know of..
Zip Zap Zoom... i am off back home.. crap...

today is my marraige aniversary.. and all i have done is talk to my wife on a noisy connection... but there are more meetings and things to setup before I sleep... or mebbe i got it upside down.. :D.. anyway one thing is for sure.. couple of weeks.. most probably no more blogs..

Disclaimers: No person/things is meant to be true if real people feel bad abt things i wrote here (i am puzzled as to what).. and any copyright violations i might have done.. not done knowingly- i have tried to avoid it.. if it still bugs u.. let me know will s/Copyright/Copyleft/g the same.