DIRECTORY Core, CoreOps; MCEccImpl: CEDAR PROGRAM IMPORTS CoreOps = BEGIN Log2: PROC[n: CARDINAL] RETURNS[log: CARDINAL_0] = {FOR n _ n, n/2 WHILE n>1 DO log _ log+1 ENDLOOP}; MainTrees: PUBLIC PROC[n: CARDINAL] RETURNS[wire: Core.Wire] = { logn: CARDINAL _ Log2[n]; span: CARDINAL; groupSize: CARDINAL; input: Core.Wire _ NewWires[n, "in"]; out: Core.Wire _ NewWires[logn+1, "out"]; fullInLt: Core.Wire _ NewWires[n, "tl"]; fullInRt: Core.Wire _ NewWires[n, "tr"]; fullOut: Core.Wire _ NewWires[n, "tm"]; subInLt: Core.Wire _ NewWires[n, "bl"]; subInRt: Core.Wire _ NewWires[n, "br"]; subOut: Core.Wire _ NewWires[n, "bm"]; gnd: Core.Wire _ NewWires[0, "Gnd"]; wire _ CoreOps.CreateWire[LIST[input,out,fullInLt,fullInRt,fullOut,subInLt,subInRt,subOut]]; out[0] _ fullOut[n/2-1] _ NewWires[0]; span _ n/2; -- span of the two xor inputs (twice the length of a node wire) FOR level: CARDINAL IN [1..logn] DO FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO phIdx: CARDINAL _ span-1 + levelIdx*2*span; IF span>1 THEN { fullInLt[phIdx] _ fullOut[phIdx-span/2] _ NewWires[0]; fullInRt[phIdx] _ fullOut[phIdx+span/2] _ NewWires[0]} ELSE { fullInLt[phIdx] _ input[phIdx] _ NewWires[0]; fullInRt[phIdx] _ input[phIdx+1] _ NewWires[0]}; ENDLOOP; span _ span/2; ENDLOOP; out[1] _ fullOut[n/4-1]; -- first subtree needs no XORs in subtree row groupSize _ n/4; FOR tree: CARDINAL IN [1..logn) DO span: CARDINAL _ n/2; out[tree+1] _ subOut[span-1 - groupSize] _ NewWires[0]; FOR span _ span, span/2 WHILE span>groupSize DO FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO phIdx: CARDINAL _ span-1 - groupSize + levelIdx*2*span; IF span > 2*groupSize THEN { subInLt[phIdx] _ subOut[phIdx-span/2] _ NewWires[0]; subInRt[phIdx] _ subOut[phIdx+span/2] _ NewWires[0]} ELSE IF groupSize>1 THEN { subInLt[phIdx] _ fullOut[phIdx - groupSize/2]; subInRt[phIdx] _ fullOut[phIdx + groupSize + groupSize/2]} ELSE { subInLt[phIdx] _ input[phIdx]; subInRt[phIdx] _ input[phIdx+2]}; ENDLOOP; ENDLOOP; groupSize _ groupSize/2; ENDLOOP; FOR index: CARDINAL IN [0..n) DO IF fullInLt [index]=NIL THEN fullInLt [index] _ gnd; IF fullInRt [index]=NIL THEN fullInRt [index] _ gnd; IF fullOut [index]=NIL THEN fullOut [index] _ NewWires[0]; IF subInLt [index]=NIL THEN subInLt [index] _ gnd; IF subInRt [index]=NIL THEN subInRt [index] _ gnd; IF subOut [index]=NIL THEN subOut [index] _ NewWires[0]; ENDLOOP}; EvenIndex: PROC[i: CARDINAL] RETURNS[even: BOOL _ TRUE] = {FOR i _ i, i/2 WHILE i#0 DO even _ ((i MOD 2)=1)#even ENDLOOP}; EncodeParity: PUBLIC PROC[n: CARDINAL] RETURNS[wire: Core.Wire] = { logn: CARDINAL _ Log2[n]; span: CARDINAL; input: Core.Wire _ NewWires[n, "in"]; out: Core.Wire _ NewWires[0, "out"]; treeInLt: Core.Wire _ NewWires[n, "l"]; treeInRt: Core.Wire _ NewWires[n, "r"]; treeOut: Core.Wire _ NewWires[n, "m"]; gnd: Core.Wire _ NewWires[0, "Gnd"]; wire _ CoreOps.CreateWire[LIST[input,out,treeInLt,treeInRt,treeOut]]; out _ treeOut[n/2-1] _ NewWires[0]; span _ n/2; -- span of the two xor inputs (twice the length of a node wire) FOR level: CARDINAL IN [1..logn) DO FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO phIdx: CARDINAL _ span-1 + levelIdx*2*span; IF span>2 THEN { treeInLt[phIdx] _ treeOut[phIdx-span/2] _ NewWires[0]; treeInRt[phIdx] _ treeOut[phIdx+span/2] _ NewWires[0]} ELSE { off: CARDINAL _ IF EvenIndex[2*n-1-phIdx] THEN 0 ELSE 1; treeInLt[phIdx] _ input[phIdx-off] _ NewWires[0]; treeInRt[phIdx] _ input[phIdx+off+1] _ NewWires[0]}; ENDLOOP; span _ span/2; ENDLOOP; FOR index: CARDINAL IN [0..n) DO IF treeInLt [index]=NIL THEN treeInLt [index] _ gnd; IF treeInRt [index]=NIL THEN treeInRt [index] _ gnd; IF treeOut [index]=NIL THEN treeOut [index] _ NewWires[0]; IF input [index]=NIL THEN input [index] _ NewWires[0]; ENDLOOP}; EncodeParity64x8: PUBLIC PROC RETURNS[wire: Core.Wire] = { wire _ EncodeParity64x8Heart[]; -- 64 data bits in high order of 72 bits FOR i: INT IN [0..wire.size) DO IF wire[i].size=72 THEN { w: Core.Wire _ CoreOps.CreateWires[72, CoreOps.GetShortWireName[wire[i]]]; FOR j: INT IN [0..72) DO w[j] _ wire[i][(j+64) MOD 72] ENDLOOP; wire[i] _ w}; ENDLOOP}; Nm: PROC[pre: Core.ROPE, i: CARDINAL] RETURNS[name: Core.ROPE] = {RETURN[NIL]}; EncodeParity64x8Heart: PUBLIC PROC RETURNS[wire: Core.Wire] = { n: CARDINAL _ 64; logn: CARDINAL _ 6; m: CARDINAL _ 8; span: CARDINAL; input: Core.Wire _ NewWires[n+m, "in"]; out: Core.Wire _ NewWires[0, "out"]; treeInLt: Core.Wire _ NewWires[n+m, "l"]; treeInRt: Core.Wire _ NewWires[n+m, "r"]; treeOut: Core.Wire _ NewWires[n+m, "m"]; gnd: Core.Wire _ NewWires[0, "Gnd"]; wire _ CoreOps.CreateWire[LIST[input,out,treeInLt,treeInRt,treeOut]]; treeOut[n/2-1] _ out; span _ n/2; -- span of the two xor inputs (twice the length of a node wire) FOR level: CARDINAL IN [1..logn) DO FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO phIdx: CARDINAL _ span-1 + levelIdx*2*span; IF span>2 THEN { treeInLt[phIdx] _ treeOut[phIdx-span/2] _ NewWires[0, Nm["T",phIdx-span/2]]; treeInRt[phIdx] _ treeOut[phIdx+span/2] _ NewWires[0, Nm["T",phIdx+span/2]]} ELSE { off: CARDINAL _ IF EvenIndex[2*n-1-phIdx] THEN 0 ELSE 1; treeInLt[phIdx] _ input[phIdx-off] _ NewWires[0, Nm["I",phIdx-off]]; treeInRt[phIdx] _ input[phIdx+off+1] _ NewWires[0, Nm["I",phIdx+off+1]]}; ENDLOOP; span _ span/2; ENDLOOP; FOR index: CARDINAL IN [0..n+m) DO IF treeInLt [index]=NIL THEN treeInLt [index] _ gnd; IF treeInRt [index]=NIL THEN treeInRt [index] _ gnd; IF treeOut [index]=NIL THEN treeOut [index] _ NewWires[0, Nm["t",index]]; IF input [index]=NIL THEN input [index] _ NewWires[0, Nm ["i",index]]; ENDLOOP}; ExtendedMainTrees64x8: PUBLIC PROC RETURNS[wire: Core.Wire] = { wire _ ExtendedMainTrees64x8Heart[]; -- 64 data bits in high order of 72 bits FOR i: INT IN [0..wire.size) DO IF wire[i].size=72 THEN { w: Core.Wire _ CoreOps.CreateWires[72, CoreOps.GetShortWireName[wire[i]]]; FOR j: INT IN [0..72) DO w[j] _ wire[i][(j+64) MOD 72] ENDLOOP; wire[i] _ w}; ENDLOOP}; ExtendedMainTrees64x8Heart: PUBLIC PROC RETURNS[wire: Core.Wire] = { n: CARDINAL _ 64; logn: CARDINAL _ 6; m: CARDINAL _ 8; logm: CARDINAL _ 3; span: CARDINAL; groupSize: CARDINAL; input: Core.Wire _ NewWires[n+m, "in"]; out: Core.Wire _ NewWires[m-1, "out"]; dp: Core.Wire _ NewWires[0, "dp"]; fullInLt: Core.Wire _ NewWires[n+m, "tl"]; fullInRt: Core.Wire _ NewWires[n+m, "tr"]; fullOut: Core.Wire _ NewWires[n+m, "tm"]; subInLt: Core.Wire _ NewWires[n+m, "bl"]; subInRt: Core.Wire _ NewWires[n+m, "br"]; subOut: Core.Wire _ NewWires[n+m, "bm"]; gnd: Core.Wire _ NewWires[0, "Gnd"]; wire _ CoreOps.CreateWire [LIST[input,out, dp,fullInLt,fullInRt,fullOut,subInLt,subInRt,subOut]]; span _ n/2; -- span of the two xor inputs (twice the length of a node wire) FOR level: CARDINAL IN [1..logn] DO FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO phIdx: CARDINAL _ span-1 + levelIdx*2*span; IF span>1 THEN { fullInLt[phIdx] _ fullOut[phIdx-span/2] _ NewWires[0, Nm["F",phIdx-span/2]]; fullInRt[phIdx] _ fullOut[phIdx+span/2] _ NewWires[0, Nm["F",phIdx+span/2]]} ELSE { last1: CARDINAL _ IF phIdx=n-2 THEN 1 ELSE 0; fullInLt[phIdx] _ input[phIdx] _ NewWires[0, Nm["I",phIdx]]; fullInRt[phIdx] _ input[phIdx+1+last1] _ NewWires[0, Nm["I",phIdx+1+last1]]}; ENDLOOP; span _ span/2; ENDLOOP; span _ m/2; FOR level: CARDINAL IN [1..logm] DO FOR levelIdx: CARDINAL IN [0..m/(2*span)) DO phIdx: CARDINAL _ n + span-1 + levelIdx*2*span; IF span>1 THEN { fullInLt[phIdx] _ fullOut[phIdx-span/2] _ NewWires[0, Nm["F",phIdx-span/2]]; fullInRt[phIdx] _ fullOut[phIdx+span/2] _ NewWires[0, Nm["F",phIdx+span/2]]} ELSE { first1: CARDINAL _ IF phIdx=n THEN 1 ELSE 0; fullInLt[phIdx] _ input[phIdx-first1] _ NewWires[0, Nm["I",phIdx-first1]]; fullInRt[phIdx] _ input[phIdx+1] _ NewWires[0, Nm["I",phIdx+1]]}; ENDLOOP; span _ span/2; ENDLOOP; fullOut[n + m/2-1] _ dp; -- Decode Parity subInLt[n+0] _ input[n-1]; subInRt[n+0] _ input[n+0+1]; -- unique bit index = 62 subInLt[n+1] _ input[n-1]; subInRt[n+1] _ input[n+1+1]; subInLt[n+2] _ input[n-1]; subInRt[n+2] _ input[n+2+1]; subInLt[n+3] _ input[n-1]; subInRt[n+3] _ input[n+3+1]; subInLt[n+4] _ input[n-1]; subInRt[n+4] _ input[n+4+1]; subInLt[n+5] _ gnd; subInRt[n+5] _ input[n+5+1]; out[0] _ fullOut[n/2-1] _ NewWires[0, Nm["O",0]]; -- 64 needs no XORs in subtree row groupSize _ n/2; FOR tree: CARDINAL IN [1..logn] DO out[tree] _ subOut[n-1 - groupSize] _ NewWires[0, Nm["O",tree]]; FOR span: CARDINAL _ n, span/2 WHILE span>groupSize DO IF span = n -- top, right arg in special location THEN { phIdx: CARDINAL _ n-1-groupSize; IF span > 2*groupSize THEN{ -- groupSize<32 subInLt[phIdx] _ subOut[phIdx-n/2] _ NewWires[0, Nm["S",phIdx-span/2]]; subInRt[phIdx] _ subOut[n-1 + tree] _ NewWires[0, Nm["S",n-1 + tree]]} ELSE { -- groupSize=32 subInLt[phIdx] _ fullOut[phIdx - groupSize/2]; subInRt[phIdx] _ subOut[n-1 + tree] _ NewWires[0, Nm["S",n-1 + tree]]} } ELSE FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO phIdx: CARDINAL _ span-1 - groupSize + levelIdx*2*span; IF span > 2*groupSize THEN { subInLt[phIdx] _ subOut[phIdx-span/2] _ NewWires[0, Nm["S",phIdx-span/2]]; subInRt[phIdx] _ subOut[phIdx+span/2] _ NewWires[0, Nm["S",phIdx+span/2]]} ELSE IF groupSize>1 THEN { subInLt[phIdx] _ fullOut[phIdx - groupSize/2]; subInRt[phIdx] _ fullOut[phIdx + groupSize + groupSize/2]} ELSE { subInLt[phIdx] _ input[phIdx]; subInRt[phIdx] _ input[phIdx+2]}; ENDLOOP; ENDLOOP; groupSize _ groupSize/2; ENDLOOP; FOR index: CARDINAL IN [0..n+m) DO IF fullInLt [index]=NIL THEN fullInLt [index] _ gnd; IF fullInRt [index]=NIL THEN fullInRt [index] _ gnd; IF fullOut [index]=NIL THEN fullOut [index] _ NewWires[0, Nm["f",index]]; IF subInLt [index]=NIL THEN subInLt [index] _ gnd; IF subInRt [index]=NIL THEN subInRt [index] _ gnd; IF subOut [index]=NIL THEN subOut [index] _ NewWires[0, Nm["s",index]]; ENDLOOP}; NewWires: PROC[n: INT _ 0, name: Core.ROPE _ NIL] RETURNS[wire: Core.Wire] = {RETURN[CoreOps.CreateWires[n, name]]}; END. MCEccImpl.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Last Edited by: Don Curry June 29, 1987 9:45:14 pm PDT Last Edited by: Gasbarro June 8, 1987 1:32:05 pm PDT Dragon Memory Controler Ecc Wire Icon implementations. MainTrees In the case of the memory controler, n=64; There is 1 full parity tree and Log2[n] subTrees. FOR t IN [0..nofSubTrees), Tree t is the parity of 2^t groups each with n/2^(t+1) bits Memory Controler: n=64, 1 parity tree and 6 subTrees SubTree 0 is the parity of one 32 bit group (msb) SubTree 5 is the parity of 32 one bit groups This implementation assumes that there are two XOR rows. The first just computes the full parity. The second row does all of the subtrees using the various group parities from the full parity tree as the inputs. The position of the XOR's in the full parity row is that of a simple flat tree. The position of the XOR's in the subtree row is similar except that each tree is shifted left by 2^t bits in order for them to fit together without conflict. Full Parity Tree SubTrees The normal way of computing the encode parity would be to first compute the check bits for the data, then compute the overall parity of data with check bits. This second operation would take Log2[Log2[n]+1] additional stages (3 for n=64 data bits). Instead we notice that the parity of the check bits is one for data bits checked by and odd number of check bits. These data bits are identified by the property of having a Ecc position index * with an odd number of 1's in it. Since the effect of each odd data bit is cancelled by the check bits, we can compute the overall parity of data with check bits by only computing the parity of all the even indexed data bits. Since one of the data bits is not present in the main trees, we make sure that it has no effect on the overall parity by assigning it an odd index (62). Remember that although everything else (wires etc) are MSB=0, Ecc indexes are LSB=0. In addition (with n=64) the data in the code word is imagined to be in the top half at Ecc indexes 127 though 65 + 62 with check bits at 64, 32, 16, 8, 4, 2 and 1, and the parity bit at 0. Puts 64 data bits in low order of 72 bits Nm: PROC[pre: Core.ROPE, i: CARDINAL] RETURNS[name: Core.ROPE] = {RETURN[IO.PutFR["%g%g", IO.rope[pre], IO.int[i]]]}; Puts 64 data bits in low order of 72 bits Include Next Level of trees (low oreder word with check bits and data bit 62) Puts 64 data bits in high order of 72 bits Decode Full Parity Tree Decode Check Parity Tree Decode Parity root SubTrees Κ ˆ– "cedar" style˜šœ™Jšœ Οmœ1™˜\JšΟb™Jšœ&˜&Jšœ Οc?˜Kšžœžœžœ ž˜#šžœ žœžœž˜,Jšœžœ˜+šžœ˜ šžœ˜Jšœ6˜6Jšœ6˜6—šžœ˜Jšœ0˜0Jšœ2˜2——Jšžœ˜—Jšœ ž˜Jšžœ˜—Jš ™Jšœ‘-˜FJšœ˜šžœžœžœ ž˜"Jšœžœ˜Jšœ7˜7šžœžœž˜/šžœ žœžœž˜,Jšœžœ(˜7šžœ˜šž˜Jšœ5˜5Jšœ5˜5—šžœžœ ˜šž˜Jšœ2˜2Jšœ:˜:—šž˜Jšœ˜Jšœ!˜!———Jšžœ˜—Jšžœ˜—Jšœž˜Jšžœ˜—šžœžœžœž˜ Jšžœžœžœ˜4Jšžœžœžœ˜4Jšžœžœžœ˜:Jšžœžœžœ˜2Jšžœžœžœ˜2Jšžœžœžœ˜8Jšžœ˜ ——J˜J™ΉJ™”J˜š Ÿ œžœžœžœžœžœ˜9Jš œžœ žœžœ žœ žœ˜@—J˜š Ÿ œžœžœžœžœ˜CJšœžœ ˜Jšœžœ˜Jšœ(˜(Jšœ'˜'Jšœ)˜)Jšœ)˜)Jšœ(˜(Jšœ'˜'Jšœžœ'˜EJšœ#˜#Jšœ ‘?˜Kšžœžœžœ ž˜#šžœ žœžœž˜,Jšœžœ˜+šžœ˜ šžœ˜Jšœ6˜6Jšœ6˜6—šžœ˜Jš œžœžœžœžœ˜8Jšœ3˜3Jšœ5˜5——Jšžœ˜—Jšœ ž˜Jšžœ˜—šžœžœžœž˜ Jšžœžœžœ˜4Jšžœžœžœ˜4Jšžœžœžœ˜:Jšžœžœžœ˜7Jšžœ˜ ——J˜J™)šŸœžœžœžœ˜:JšœŸœ,˜Hšžœžœžœž˜šžœžœ˜JšœJ˜JJš žœžœžœ žœžœžœ˜?Jšœ ˜ —Jšžœ˜ ——J˜Jš Ÿœžœ žœžœžœ žœ˜Oš Ÿœžœ žœžœžœ žœ™@Jš œžœžœžœ žœ ™4—šŸœžœžœžœ˜?Jšœžœ˜Jšœžœ˜Jšœžœ˜Jšœžœ˜Jšœ*˜*Jšœ(˜(Jšœ+˜+Jšœ+˜+Jšœ*˜*Jšœ(˜(Jšœžœ'˜EJšœ˜Jšœ ‘?˜Kšžœžœžœ ž˜#šžœ žœžœž˜,Jšœžœ˜+šžœ˜ šžœ˜JšœL˜LJšœL˜L—šžœ˜Jš œžœžœžœžœ˜8JšœF˜FJšœJ˜J——Jšžœ˜—Jšœ˜Jšžœ˜—šžœžœžœ ž˜"Jšžœžœžœ˜4Jšžœžœžœ˜4Jšžœžœžœ.˜IJšžœžœžœ-˜GJšžœ˜ ——J˜J™J™)šŸœžœžœžœ˜?JšœM˜Mšžœžœžœž˜šžœžœ˜JšœJ˜JJš žœžœžœ žœžœžœ˜?Jšœ ˜ —Jšžœ˜ ——J˜JšœM™MJ™*šŸœžœžœžœ˜DJšœžœ˜Jšœžœ˜Jšœžœ˜Jšœžœ˜Jšœžœ˜Jšœ žœ˜Jšœ*˜*Jšœ)˜)Jšœ&˜&Jšœ,˜,Jšœ,˜,Jšœ+˜+Jšœ+˜+Jšœ+˜+Jšœ*˜*Jšœ(˜(šœ˜JšœžœB˜G—Jš ™Jšœ ‘?˜Kšžœžœžœ ž˜#šžœ žœžœž˜,Jšœžœ˜+šžœ˜ šžœ˜JšœL˜LJšœL˜L—šžœ˜Jš œžœžœ žœžœ˜-Jšœ?˜?JšœN˜N——Jšžœ˜—Jšœ˜Jšžœ˜—Jš ™Jšœ ˜ šžœžœžœ ž˜#šžœ žœžœž˜,Jšœžœ ˜/šžœ˜ šžœ˜JšœL˜LJšœL˜L—šžœ˜Jš œžœžœ žœžœ˜,JšœK˜KJšœC˜C——Jšžœ˜—Jšœ˜Jšžœ˜—Jš ™Jšœ‘˜)J˜Jš ™Jšœ8‘˜PJšœ7˜7Jšœ7˜7Jšœ7˜7Jšœ7˜7Jšœ2˜2Jšœ2‘"˜TJšœ˜šžœžœžœ ž˜"Jšœ@˜@šžœžœ žœž˜6šžœ ‘%˜1šžœž˜Jšœžœ˜ šžœ˜šžœ˜JšœG˜GJšœF˜F—šžœ˜Jšœ.˜.JšœH˜H———š žœžœ žœžœž˜1Jšœžœ(˜7šžœ˜šžœ˜JšœJ˜JJšœJ˜J—šžœžœ ˜šžœ˜Jšœ2˜2Jšœ:˜:—šžœ˜Jšœ˜Jšœ!˜!———Jšžœ˜——Jšžœ˜—Jšœ˜Jšžœ˜—šžœžœžœ ž˜"Jšžœžœžœ˜4Jšžœžœžœ˜4Jšžœžœžœ.˜IJšžœžœžœ˜2Jšžœžœžœ˜2Jšžœžœžœ-˜GJšžœ˜ ——J˜š Ÿœžœžœžœžœžœ˜MJšœžœ ˜'—J˜Jšžœ˜J˜J˜—…—',=Ό