Home     Forum     Projects     Experiments     Circuits     Theory     BLOG     PIC Tutorials     Time for Science

### Author Topic: Error corection  (Read 12808 times)

0 Members and 1 Guest are viewing this topic.

#### d_click

• Guest
##### Error corection
« on: August 28, 2008, 02:52:20 AM »
Hi friends

I am making a bus using microcontrollers. This bus will run round my house and i will operate from computer some lights and stuff.

For this bus, i need to make a communication protocol. I could use some ready made but i can try making mine.
For this protocol, i a mthinking of using a correction engine. Odd and even is one choice.
Does someone else have another idea?

Any ideas accepted with plesure!

#### merox_0032

• Guest
##### Re: Error corection
« Reply #1 on: August 28, 2008, 11:16:38 AM »
send it two times

#### Mercury

• Guest
##### Re: Error corection
« Reply #2 on: August 28, 2008, 15:54:36 PM »
send it two times
Scientists have spent money and time to improve error corection methods, only to aviod sending twice the data...

#### Supernova

• Full Member
• Posts: 149
##### Re: Error corection
« Reply #3 on: August 30, 2008, 13:38:15 PM »
Of course not 2 times. And if you send it 2 times and they are not correct then you so what? You send it anoter 2 times?

One widely used in memories error correction is the Hamming error correction.
A n-bit byte will be injected with k bits. The number k depends on the number of bits. The injected bits will cover the power of 2 positions in the byte. For an 8-bit byte for example, there will be 4 injected bits, in positions 1,2,4 and 8.

Example:
suppose we have the byte 11000100. It is an 8-bit byte thus 4 bits will be injected. We name them P1 P2 P4 and P8. The final byte will be 12bits length:

 1 2 3 4 5 6 7 8 9 10 11 12 P1 P2 1 P4 1 0 0 P8 0 1 0 0

To calculate the injected bits we use the XOR for the following bits of the 12-bit byte:
P1= XOR of bits [3,5,7,9,11]
P2= XOR of bits [3,6,7,10,11]
P4= XOR of bits [5,6,7,12]
P8= XOR of bits [9,10,11,12]

Our previous byte will become:

 1 2 3 4 5 6 7 8 9 10 11 12 0 0 1 1 1 0 0 1 0 1 0 0

Checking the byte:
To check the byte received, you do:

C1=XOR of bits [1,3,5,7,9,11]
C2=XOR of bits [2,3,6,7,10,11]
C3=XOR of bits [4,5,6,7,12]
C4=XOR of bits [8,9,10,11,12]

And this will produce a 4-bit number: C=C8C4C2C1

If c==0, no error occured.

But if C!==0, then the number C will determine which bit is fault.
Example:
C=0000 ; No error
C=0001 ; 1st bit is wrong
C=0101 ; 5th bit is wrong

Then you correct this bit by xoring it and the byte is ok.

The above code will check for a single error. What if there is error in 2 bits? Then you need another bit injection, the P13. This will increase the size of 1 more bit. the P13 will be:
P13= XOR of all 12 bits.
To check the data received, you use the same C number as before in conjuction with P13 as follows:

If C==0 and P13==0 : No error
If C!==0 and P==1: Single error that can be fixed
if C!==0 and P==0 : Double error that can be found but not fixed.
if C==0 and P13==1 : Error in P13

Hope this will meet your demands.

#### kam

• Hero Member
• Posts: 1849
##### Re: Error corection
« Reply #4 on: August 30, 2008, 16:59:19 PM »
Supernova that is very good. I will add it to the All about PICs pages.

#### d_click

• Guest
##### Re: Error corection
« Reply #5 on: August 31, 2008, 18:30:19 PM »
THIS IS BETETR THAN I EXPECT!!!!

COOL SUPERNOVA THANX
Thisis better than the best solution i had thought!!!!! It is absolutely great! Thanx

#### Supernova

• Full Member
• Posts: 149
##### Re: Error corection
« Reply #6 on: September 02, 2008, 17:04:34 PM »
Anytime. That's why we are here

#### kammenos

• Guest
##### Re: Error corection
« Reply #7 on: September 02, 2008, 18:01:46 PM »
This is a very nice correction engine but for your case, for communication, you should consider sending packets of data, for example send 4 bytes each time, end then the client will answer with the CRC and the host will confirm. That will be much faster.
The Hamming code is for storing data. Because memories will not check crc and will not answer, they will only store data. So, this is a way to check if the stored data are correct.

#### Supernova

• Full Member
• Posts: 149
##### Re: Error corection
« Reply #8 on: September 03, 2008, 10:21:58 AM »
This is a very nice correction engine but for your case, for communication, you should consider sending packets of data, for example send 4 bytes each time, end then the client will answer with the CRC and the host will confirm. That will be much faster.
The Hamming code is for storing data. Because memories will not check crc and will not answer, they will only store data. So, this is a way to check if the stored data are correct.
Yes maybe you are right. If you need to transmit packages yes. But i suppose he will send one command like "open light". That will be one byte.. Or maybe two bytes "Dim light - 70%". That would not be a packet...

#### kammenos

• Guest
##### Re: Error corection
« Reply #9 on: September 03, 2008, 18:11:47 PM »
You've got a point here.

#### d_click

• Guest
##### Re: Error corection
« Reply #10 on: September 05, 2008, 19:13:55 PM »
I think that hamming error correction fits me best. I do not really have any packets to transmit. I will only transmit some bits of data. These will be 7 or 8 bits. If they become 13 this is not really a problem...

#### Mercury

• Guest
##### Re: Error corection
« Reply #11 on: September 10, 2008, 00:16:40 AM »
Checking the net i found that hamming code is for storage systems such as memories. You should better find another way that will be more faster and more reliable. One question. you have for example 10 lights that you want to actuate with one button. What if one light creates error?

This is not as easy as it seems to be

#### d_click

• Guest
##### Re: Error corection
« Reply #12 on: September 10, 2008, 08:03:28 AM »
Checking the net i found that hamming code is for storage systems such as memories. You should better find another way that will be more faster and more reliable. One question. you have for example 10 lights that you want to actuate with one button. What if one light creates error?

This is not as easy as it seems to be

Yes, there will be more than ones to acccepts the data. if no error occurs, then no response. But s error occurs, then the one witht he error will ask for a resend

#### kam

• Hero Member
• Posts: 1849
##### Re: Error corection
« Reply #13 on: September 14, 2008, 16:41:32 PM »
You may also use something as the following:

There are devices that may POST a command and devces that EXECUTE a command. The post devices will be for example the switches, the timers etc etc etc. The EXECUTE devices will be the lights for example. Each PD (post device) will post one ore more commands and so the ED will execute one ore more commands. But ED will listen to specific commands. So for example, one command would be 00x01h. This command for instance will be the "Open light 1" and the 00x02h would be "Close light 1". This means that the number of commands you may have depends on the bit length of your command byte. A 8-bit command may get up to 255 commands. Enough for a house but you may have 9-bit bytes or 10-bit bytes. That is up to you.

When one PD send a command over the bus, it will expect of a confirmation. This is up to you but you may do this:
1. The PD send the command
2. All ED devices will listen to the command and check if found any error
2.a.          If NO error then will check if they should run this command
2.a.I.               If they run the command, they will answer to the bus with an acknowledge (that could be 00x00h)
2.b.          If error IS answer to the bus with an error (that could be 00xFF)
3. The PD that send the command will wait for the answers. This is importans: ALL ANSWERS MUST BE SEND EXACTLY THE SAME TIME!!! So, if for example all the EDs that will run the command have no error, then they wil answer all together with 00x00 simultaneously and the PD will read this 00x00 and all wil be ok. But if one ore more EDs have error, then they will send the 00xFF and the PD will not read 00x00 but 00xFF. If it reads an error reply, then the PD may resend for example 3 times.

Check it out

#### d_click

• Guest
##### Re: Error corection
« Reply #14 on: September 15, 2008, 21:36:15 PM »
JESUS this is i think too complicated for me. I will use only the simple method from supernova.