AN427 Freescale Semiconductor, Inc. MC68HC11 EEPROM Error Co
|
|
|
Top Searches for this datasheet
Order this document AN427/D
AN427
Freescale Semiconductor, Inc.
MC68HC11 EEPROM Error Correction Algorithms
Richard Soja Motorola Ltd. East Kilbride, Glasgow
Introduction
This application note describes technique correcting 1-bit errors detecting 2-bit errors block data ranging from bits length. technique applied modified version Hamming code been implemented entirely Additional functions have been provided program read EEPROM (electrically erasable programmable read-only memory) M68HC11 microcontroller unit using error encoding decoding algorithms.
Encoding Decoding Algorithms
Some texts (see References [2]) describe simultaneous equations calculate check bits Hamming distance-3 error correcting codes. These codes named because there least three differences between each valid code available codes. codes relatively easy generate used correct 1-bit errors. However, their main drawback that 2-bit errors occur, then correction will made erroneously. This because condition 2-bit errors corresponds exactly with 1-bit error from another valid code.
Motorola, Inc., 1990, 2000
AN427
More Information This Product, www.freescale.com
Freescale Semiconductor, Inc. Application Note
technique described here based algorithmic strategy which produces Hamming distance-4 codes over range data bits. This type code capable correcting single-bit errors detecting 2-bit errors. Alternatively, errors only detected, without correction, then three errors detected. reason this that condition error code corresponds 1-bit error from adjacent valid code. implication this that algorithms used correct errors, then 3-bit error will corrected erroneously flagged 1-bit error. program divided into three modules, plus header file. example: EECOR1.C This main program segment serves only illustrate method calling checking algorithms. HAMMING.C This module contains functions which encode decode data. EEPROG.C This module contains EEPROM programming functions tailored M68HC11 MCU. HC11REG.H This header file which contains M68HC11 input/output (I/O) register names defined structure.
Freescale Semiconductor, Inc.
Implementation Error Correction Strategy
basic principle decoding error correcting codes parity check matrix, generate syndrome word which identifies error. matrix generated follows: Identify many data bits needed. example: data bits standard equation derive number check bits required: number check bits number data bits, then Hamming bound satisfied:
AN427 More Information This Product, www.freescale.com MOTOROLA
Application Note Implementation Error Correction Strategy
simple understand this equation holds true follows: generate check code which able identify where single error occurs stream, then check code must have least same number unique combinations there bits stream, plus extra combination indicate that error occurred. example, total number data plus check bits were seven, then check code must consist three bits cover range seven plus extra indicate error all.
Freescale Semiconductor, Inc.
this example, then rearranging earlier equation: solve just select values starting say, evaluating until bound reached. This method implemented algorithm function InitEncode() Module HAMMING.C. solution Note that this value exceeds Hamming bound, which means that additional data bits added stream, thus increasing efficiency code. fact, maximum number data bits this case. parity matrix, created from "horizontally oriented" binary table. number columns b12) matrix correspond total number data check bits number rows number check bits.
i.e.
Because matrix this form simply truncated 4-bit binary table, easily generated algorithm.
AN427 MOTOROLA More Information This Product, www.freescale.com
Freescale Semiconductor, Inc. Application Note
position check bits within encoded word position single columns remaining bits correspond data bits D8).
i.e.
Freescale Semiconductor, Inc.
Each check generated taking each turn modulo-2 adding bits with them xcept check positions. i.e. D1+D2+D4+D5+D7 D1+D3+D4+D6+D7 D2+D3+D4+D8 D5+D6+D7+D8
syndrome, binary weighted value check bits. i.e. 1*C1+2*C2+4*C3+8*C4
error position (i.e. column) determined value syndrome word, provided zero. zero syndrome means error occurred. Note that this error correction technique correct errors either data check bits, which necessarily case with certain other error correction strategies. advantage this method, where check bits interspersed binary manner throughout code word, that error position calculated algorithm. important point note that parity check matrix described earlier generates Hamming distance-3 codes, which means that errors will cause erroneous correction. This fixed adding extra parity check bit, which modulo-2 addition data check bits together. i.e.
code word then becomes:
AN427 More Information This Product, www.freescale.com MOTOROLA
Application Note Efficiency
determine uncorrectable error occurred (i.e. errors) received word, extra parity tested. syndrome non-zero parity wrong, then correctable error occurred. syndrome non-zero parity correct, then uncorrectable error occurred.
Efficiency
following table lists relative efficiencies this algorithm, against data size.
Data Bits Encoded Bits Efficiency
Freescale Semiconductor, Inc.
implementation these techniques given Module HAMMING.C. order maintain orthogonality EEPROM algorithms, encoded data used functions Module EEPROG.C forced either 1-byte 2-byte (word) sizes. This also eliminates complexities packing unpacking data partially filled bytes.
AN427 MOTOROLA More Information This Product, www.freescale.com
Freescale Semiconductor, Inc. Application Note Conclusions
this application note, encoding algorithm's generator matrix same parity check matrix. functions <read> <write> Module HAMMING.C return status value which indicates whether data errors, corrected error, erroneously corrected errors. This means that status value then data assumed good. status value then data will bad. Alternatively, functions used error detection only, without correction. this case, status value corresponds either 3-bit errors, while status value indicates that 2-bit errors have occurred. using functions listed this application note, encoded data size easily changed dynamically. this, function <InitEncode> must called with required data size. global variables used encoding, decoding, EEPROM programming reading functions automatically updated. This allows encoding error correction process virtually transparent user. addition, functions <write> <read> will automatically increment address pointer correct encoded data size <InitEncode>. This simplifies structure loops program read back data. Example code provided Module EECOR1.C. encoding decoding algorithms listed here applied other forms data, such that used serial communications parallel data transfers. incorporating error correction detection-only schemes described this application note, integrity data storage transfer greatly improved. impact EEPROM usage increase effective reliability extend useful life beyond manufacturer's guaranteed specifications.
Freescale Semiconductor, Inc.
AN427 More Information This Product, www.freescale.com MOTOROLA
Application Note References
References
Carlson, Communication Systems, Chapter McGraw-Hill. Harman, Principles Statistical Theory Communication, Chapter McGraw-Hill.
Module EECOR1.C
Freescale Semiconductor, Inc.
Tests EEPROM error detection using modified hamming encoding scheme. typedef unsigned char byte; typedef unsigned word;
Global variables used main byte word data: /*External global variables extern byte CodeSize;
number bits encoded data
External Functions extern byte read(word *data,byte **addr); Function returns error status extern byte write(word data,byte **addr); Table Status returned read write functions Returned Status Condition errors detected corrected. error detected corrected. errors detected, correction erroneous. Notes: When returned value function <read> will returned value variable <data> inability correctly correct errors. <read> also automatically increments address pointer passed next memory space. incremented value takes into account actual size encoded data. i.e. either byte increment. Function <write> also performs read update return error status. This gives immediate indication whether write successful. <write> also automatically increments address pointer passed next free memory space. incremented value takes into account actual size encoded data. i.e. either byte increment. main CodeSize=InitEncode(11);
code size (less needed data bits Initialise EEPROM start address 'erase' EEPROM Function successful Error<>2 Reset EEPROM address Write 0x5aa increment ee_addr
ee_addr=(byte *)0xb600; for(i=1;i<=0x10;i++) Error=write(0x7ff,&ee_addr); ee_addr=(byte *)0xb600; Error=write(0x5aa,&ee_addr);
AN427 MOTOROLA More Information This Product, www.freescale.com
Freescale Semiconductor, Inc. Application Note
Error=write(0x255,&ee_addr); CodeSize=InitEncode(4); start_addr=ee_addr; for(i=1;i<0x10;i<<=1) Error=write(i,&ee_addr); end_addr=ee_addr; ee_addr=start_addr; while (ee_addr<end_addr) Error=read(&data,&ee_addr); main Write 0x255 next available address Change number data bits Save start address this data Program 'walking Save address
Read back data <data> good Error=0
Freescale Semiconductor, Inc.
Module HAMMING.C
Modules Generate hamming codes distance data sizes range bits. upper bound limited encoded word type range bits). Corrects error position (check data), detects errors position. After execution <Decode> function, global variable <ErrFlag> updated indicate level error correction. i.e. ErrFlag Condition errors detected corrected. error detected corrected. errors detected, correction erroneous.
Note that when ErrFlag function <Decode> will return value, inability correctly correct errors. #define #define typedef typedef TRUE FALSE unsigned char byte; unsigned word;
byte Function prototypes byte OddParity(word Code); word Power2(byte byte InitEncode(byte DataLength); word MakeCheck(word Data); word Encode(word Data); word Decode(word Code); byte OddParity(Code) word Code; Returns TRUE Code parity, otherwise returns FALSE byte p=TRUE; While (Code!=0)
AN427 More Information This Product, www.freescale.com MOTOROLA
Application Note Module HAMMING.C
(Code p=!p; Code>>=1; return(p); word Power2(e) byte Returns word signed char P2=1; ((signed char) (e)<0) return(0); else (i=1;i<=(signed char) (e);i++) P2<<=1; return(P2); byte InitEncode(DataLength) byte DataLength; Returns minimum number total bits needed provide Hamming distance codes from data size defined passed variable <DataLength>. This value also updates global variable <DataSize>. i.e. finds minimum solution (k+m) inequality: addition, updates global variable <EncodedSize> reflect number bytes encoded data. <EncodedSize> will either
Freescale Semiconductor, Inc.
byte CheckLength,i; DataSize=DataLength; DataSize used other functions this module CheckLength=1; while CheckLength++; i=CheckLength+DataLength; EncodedWord=i byte sized, word sized return(CheckLength+DataLength); word MakeCheck(Data) word Data; Returns check word Data, based global variables <DataSize> <CheckSize>. parity matrix generated simple loop. byte word DataMask;
AN427 MOTOROLA More Information This Product, www.freescale.com
Freescale Semiconductor, Inc. Application Note
Freescale Semiconductor, Inc.
Check=0; CheckMask=1; CheckSize=CodeSize-DataSize; (i=1;i<=CheckSize;i++) CheckValue=FALSE; DataMask=1 (H=1;H<=CodeSize;H++) ((0x8000 H)!=0) Column with single CheckMask !=0) CheckValue^=((DataMask Data) !=0); DataMask<<=1; (CheckValue) Check|=CheckMask; CheckMask<<=1; return(Check); word Encode (Data) word Data; Returns encoded word, consisting check bits concatenated most significant <Data>. single parity concatenated Encoded word increase hamming bound from provide error detection well correction. Uses global variables <Datasize> <CodeSize> determine concatenating positions. word Code; Code=Data (MakeCheck(Data)<<DataSize); (OddParity(Code)) Code|=Power2(CodeSize); return(Code); word Decode(Code) word Code; Returns error corrected data word, decoded from <Code>. Uses global variable <DataSize> determine position check bits <Code>. Updates global variable <ErrFlag> indicate error status i.e.: ErrFlag Status errors found Single error corrected Double error invalid correction word byte ErrFlag=0; ParityBit=Code Power2(CodeSize); DataMask=Power2(DataSize)-1; Data=Code DataMask; CheckSize=CodeSize-DataSize;
Extract parity Make data mask Extract parity bits. Extract check bits,
AN427 More Information This Product, www.freescale.com MOTOROLA
Application Note Module EEPROG.C
Check=(Code>>DataSize) (Power2(CheckSize)-1; ErrorCheck=MakeCheck(Data); Syndrome=Check ErrorCheck; (Syndrome>0) ErrFlag++; H=0; DataPos=0; CheckPos=DataSize; DataBit=TRUE; while ((H!+Syndrome) (DataPos<DataSize)) H++; DataBit=(0x8000 (DataBit) DataPos++; else CheckPos++; (DataBit) Code^=Power2(DataPos-1); else Code^=Power2(CheckPos-1); Code|=ParityBit; (OddParity(Code)) ErrFlag++; return(Code DataMask);
ignoring parity.
position error. Increment flag error exists
Identify which data code error.
Freescale Semiconductor, Inc.
Module EEPROG.C
/*Module program MC68HC11 EEPROM Contains <read> <write> functions encode decode data formatted modified hamming scheme. #include <HC11REG.H> #define regbase (*(struct HC11IO 0x1000) #define #define typedef typedef eras 0x16 writ 0x02 unsigned char byte; unsigned word;
union twobytes word byte b[2]; udata; extern byte EncodedWord,ErrFlag; Function prototypes extern word Encode(word Data); extern word Decode(word Code); void void void byte byte
Word stored MSB,
delay(word count); eeprog(byte val,byte byt,byte *addr,word count); program(byte byt,byte *addr); read(word *data,byte **addr); write(word data,byte **addr);
void delay(count) word count;
timeout period
AN427 MOTOROLA More Information This Product, www.freescale.com
Freescale Semiconductor, Inc. Application Note
regbase.TFLG1=0x80; do;while ((regbase.TFLG1 0x80)==0); clear pending flag. Wait timeout flag.
Freescale Semiconductor, Inc.
void eeprog(val,byt,addr,count) byte val; byte byt; byte *addr; word count; regbase.PPROG=val; *addr=byt; ++regbase.PPROG; (count<100) count=100; delay(count); -regbase.PPROG; regbase.PPROG=0; void program(byt,addr) byte byt; byte *addr; eeprog(eras,byt,addr,20000); eeprog(writ,byt,addr,20000); byte read(data,addr) word *data; byte **addr; udata.b[1]=*(*addr)++; (EncodedWord) udata.b[0]=*(*addr)++; else udata.b[0]=0; *data=Decode(udata.w); return(ErrFlag); byte write(data,addr) word data; byte **addr; byte *oldaddr; udata.w=Encode(data); oldaddr=*addr; program(udata.b[1],(*addr)++); (EncodedWord) program(udata.b[0],(*addr)++);
determines Erase Write operation byte programmed addr address encoded byte EEPROM count number clock delays Enable address/data latches Write value required eeprom location Enable voltage pump Allow software overhead wait Disable pump,then addr/data latches
First erase byte Then write value
Read back data first, address word stored then read address next call this function else only byte stored, clear
Decode data, which updates <ErrFlag>, return ErrFlag
Encode data. Save initial address verification. Program first allow either byte encoded data word sized data,& address Return <ErrFlag> calling segment
AN427 More Information This Product, www.freescale.com MOTOROLA
Application Note HC11REG.H
HC11REG.H
Freescale Semiconductor, Inc.
HC11 structure registers MC68HC11 struct HC11IO unsigned char PORTA; Port input only, output only unsigned char Reserved; unsigned char PIOC; Parallel control unsigned char PORTC; Port unsigned char PORTB; Port Output only unsigned char PORTCL; Alternate port latch unsigned char Reserved1; unsigned char DDRC; Data direction port unsigned char PORTD; Port unsigned char DDRD; Data direction port unsigned char PORTE; Port Timer Section unsigned unsigned unsigned unsigned unsigned unsigned unsigned unsigned unsigned char char char CFORC; OC1M; OC1D; TCNT; TIC1; TIC2; TIC3; TOC1; TOC2; TOC3; TOC4; TOC5; TCTL1; TCTL2; TMSK1; TFLG1; TMSK2; TFLG2; Compare force mask data Timer counter Input capture Input capture Input capture Output compare Output compare Output compare Output compare Output compare Timer control register Timer control register Main timer interrupt mask Main timer interrupt flag Main timer interrupt mask Main timer interrupt flag
char char char char char char
Pulse Accumulator Timer Control unsigned char unsigned char PACTL; PACNT Pulse control Pulse count
registers unsigned char unsigned char unsigned char SPCR; SPSR; SPDR; control register status register data register
registers unsigned unisgned unisgned unisgned unsigned char char char char char BAUD; SCCR1; SCCR2; SCSR; SCDR; control register Array result registers baud rate control control register control register status register data register
registers unsigned char unsigned char ADCTL; ADR[4];
Define each result register
AN427 MOTOROLA More Information This Product, www.freescale.com
Freescale Semiconductor, Inc. Application Note
#define #define #define #define unsigned char adr1 adr2 adr3 adr4 ADR[0] ADR[1] ADR[2] ADR[3] Reserved expansion System configuration options Arm/Reset timer circuitry EEPROM programming control Highest priority i-bit misc mapping register Factory TEST control register EEPROM cell COP,ROM,& EEPROM
Rsrv[4];
System Configuration unsigned unsigned unsigned unsigned unsigned unsigned unsigned char char char char char char char OPTION; COPRST; PPROG; HPRIO; INIT; TEST1; CONFIG;
Freescale Semiconductor, Inc.
structure HC11
AN427 More Information This Product, www.freescale.com MOTOROLA
Application Note HC11REG.H
Freescale Semiconductor, Inc.
AN427 MOTOROLA More Information This Product, www.freescale.com
Freescale Semiconductor, Inc. Application Note
Freescale Semiconductor, Inc.
Motorola reserves right make changes without further notice products herein. Motorola makes warranty, representation guarantee regarding suitability products particular purpose, does Motorola assume liability arising application product circuit, specifically disclaims liability, including without limitation consequential incidental damages. "Typical" parameters which provided Motorola data sheets and/or specifications vary different applications actual performance vary over time. operating parameters, including "Typicals" must validated each customer application customer's technical experts. Motorola does convey license under patent rights rights others. Motorola products designed, intended, authorized components systems intended surgical implant into body, other applications intended support sustain life, other application which failure Motorola product could create situation where personal injury death occur. Should Buyer purchase Motorola products such unintended unauthorized application, Buyer shall indemnify hold Motorola officers, employees, subsidiaries, affiliates, distributors harmless against claims, costs, damages, expenses, reasonable attorney fees arising directly indirectly, claim personal injury death associated with such unintended unauthorized use, even such claim alleges that Motorola negligent regarding design manufacture part. Motorola registered trademarks Motorola, Inc. Motorola, Inc. Equal Opportunity/Affirmative Action Employer.
reach USA/EUROPE/Locations Listed: Motorola Literature Distribution, P.O. 5405, Denver, Colorado 80217, 1-303-675-2140 1-800-441-2447. Customer Focus Center, 1-800-521-6274 JAPAN: Motorola Japan Ltd.; SPS, Technical Information Center, 3-20-1, Minami-Azabu, Minato-ku, Tokyo, 106-8573 Japan. 81-3-3440-8573 ASIA/PACIFIC: Motorola Semiconductors H.K. Ltd.; Silicon Harbour Centre, King Street, Industrial Estate, N.T., Hong Kong. 852-26668334 MfaxTM, Motorola Back System: RMFAX0@email.sps.mot.com; http://sps.motorola.com/mfax/; TOUCHTONE, 1-602-244-6609; Canada ONLY, 1-800-774-1848 HOME PAGE: http://motorola.com/sps/ Mfax trademark Motorola, Inc.
Motorola, Inc., 2000
AN427/D More Information This Product, www.freescale.com
Other recent searches
MMBT3906WG - MMBT3906WG MMBT3906WG Datasheet
ISO8802-3 - ISO8802-3 ISO8802-3 Datasheet
HT48RA5 - HT48RA5 HT48RA5 Datasheet
HT48CA5 - HT48CA5 HT48CA5 Datasheet
Bi10U-EM30H-AP6X-H1141 - Bi10U-EM30H-AP6X-H1141 Bi10U-EM30H-AP6X-H1141 Datasheet
1SS372 - 1SS372 1SS372 Datasheet
Privacy Policy | Disclaimer
© 2012 Datasheet Archive
