• AVR Freaks

Parity challenge

Author
Guest
Super Member
  • Total Posts : 80503
  • Reward points : 0
  • Joined: 2003/01/01 00:00:00
  • Location: 0
  • Status: online
2002/09/03 06:36:00 (permalink)
0

Parity challenge




I got a very short parity generation algorithm, using John's idea and the following observation: when you increment a two bit word B1-B0, the MSB becomes the XOR of the two bits:



swapf X, w ; John's idea: reducing byte to nibble

xorwf X, w

addlw 41H ; bit 1 becomes B0^B1 and bit 7 becomes B6^B7

iorlw 7CH ; for carry propagation from bit 1 to bit 7

addlw 2 ; Done! the parity bit is bit 7 of W

addlw 80H ; getting the parity in Carry



Here are the results, for the time being:



Dave 10 lines, 52 cycles, 1 RAM, 21-8-02

John 10 lines, 10 cycles, 1 RAM, 22-8-02

John&Daniel 6 lines, 6 cycles, 0 RAM, 3-9-02



Daniel


#1

10 Replies Related Threads

    ric
    Super Member
    • Total Posts : 29935
    • Reward points : 0
    • Joined: 2003/11/07 12:41:26
    • Location: Australia, Melbourne
    • Status: offline
    Parity challenge 2002/09/12 16:30:00 (permalink)
    0

    Brilliant! Microchip should publish this in an Application Note!

    It just shows what happens when great thinkers band together. :~)












    CheckParity:
    swapfX, w; John's idea: reducing byte to nibble
    xorwfX, w
    addlw41H; bit 1 becomes B0^B1 and bit 7 becomes B6^B7
    iorlw7CH; for carry propagation from bit 1 to bit 7
    addlw2; Done! the parity bit is bit 7 of W
    addlw80H; getting the parity in Carry
    return


    But, surely the last two instructions can be merged into "addlw 82H"

    Edit: No they can't. Adding 80H to move bit 7 into Carry depends upon carry from the addlw 2 being lost.

    #2
    maxwell
    Super Member
    • Total Posts : 1510
    • Reward points : 0
    • Joined: 2003/11/07 12:35:27
    • Status: offline
    Parity challenge 2002/09/16 13:04:00 (permalink)
    0

    On 9/12/2002 4:30:00 PM, Richard Collett wrote:





    iorlw7CH; for carry propagation from bit 1 to bit 7

    addlw2; Done! the parity bit is bit 7 of W

    addlw80H; getting the parity in Carry



    >

    >But, surely the last two

    >instructions can be merged

    >into "addlw 82H"

    >Edit: No they can't. Adding

    >80H to move bit 7 into Carry

    >depends upon carry from the

    >addlw 2 being lost.



    I don't think so. There is either a carry from the addlw 2 or not. If not, bit 7 is unchanged, and adding 0x80 in the same instruction gives the correct answer in CY.



    If there is a carry from bit 2, bit 7 toggles. The carry becomes the previous value of bit 7, but we don't care about that, because the new bit 7 is the answer, not the old bit 7. Now add 0x80; the result is that bit 7 is now the sum of the old bit 7, the carry from bit 2, and the 1 from the 0x80. The final carry is generated from the sum



    (old bit 7) + (carry from bit 2) + 1



    Combining addlw 0x02 with addlw 0x80 to get addlw 0x82 does not differ from an "add with carry" operation. The add is between the old bit 7 and the 1, and the carry is from bit 2.



    John N. Power


    POWER TECHNOLOGIES


    #3
    ric
    Super Member
    • Total Posts : 29935
    • Reward points : 0
    • Joined: 2003/11/07 12:41:26
    • Location: Australia, Melbourne
    • Status: offline
    Parity challenge 2002/11/13 15:53:00 (permalink)
    +1 (1)

    On 9/16/2002 1:04:00 PM, John Power wrote:

    ---[snip]---

    >I don't think so.

    ---[snip]---

    >Combining addlw 0x02 with addlw 0x80 to

    >get addlw 0x82 does not differ from an

    >"add with carry" operation. The add is

    >between the old bit 7 and the 1, and the

    >carry is from bit 2.

    ---------------------------------------

    Sorry about the delay, I only just checked back into the conference.

    Sorry, John, you are wrong. You have fallen into the same error I did originally.

    Just try this routine with the value 05 and the "addlw 82" version fails. (05 has even parity)



    Here is what W and carry hold after each step of each version.


    Correct version:
    W=50, C=?  SWAPF x,W 
    W=55, C=? XORWF x,W
    W=96, C=0 ADDLW 41h
    W=FE, C=0 IORLW 7Ch
    W=00, C=1 ADDLW 2
    W=80, C=0 ADDLW 80h

    Bad version:
    W=50, C=?  SWAPF x,W 
    W=55, C=? XORWF x,W
    W=96, C=0 ADDLW 41h
    W=FE, C=0 IORLW 7Ch
    W=80, C=1 ADDLW 82h

    (I originally discovered my error by writing a BASIC program to test the two different methods on every value from 00 to FF.
    The "addlw 82h" version gives the wrong result 128 times out of 256. The longer version gives the correct result 256 times. QED)

    #4
    maxwell
    Super Member
    • Total Posts : 1510
    • Reward points : 0
    • Joined: 2003/11/07 12:35:27
    • Status: offline
    Parity challenge 2002/11/18 13:49:11 (permalink)
    0

    Yes, you're right. If you add 2 to 255 (modulo 256), you get 1 with a carry. Adding two 1's in sequence gives first 0 with a carry, then 1 with no carry. The sum is the same in both cases, and there is a carry in both cases, but the carry occurs in a different place. The result is that the final value of carry is not the same.



    John N. Power


    POWER TECHNOLOGIES


    #5
    Guest
    Super Member
    • Total Posts : 80503
    • Reward points : 0
    • Joined: 2003/01/01 00:00:00
    • Location: 0
    • Status: online
    Parity challenge 2002/09/15 12:12:00 (permalink)
    0

    A trick old as the planet itself, but it works!



    My idea: why to move the bit into carry?

    we can decide after the 5th instruction what to do, because the result is done.



    Seems that you're gonna be the new PIC master!

    Welcome to the team, and take the lead!



    Mario.
    #6
    supercat
    Starting Member
    • Total Posts : 43
    • Reward points : 0
    • Joined: 2003/11/07 12:36:47
    • Status: offline
    Parity challenge 2002/09/16 09:32:00 (permalink)
    0

    //we can decide after the 5th instruction what to do, because the result is done.//



    On the 16-bit PICs (both 17xx and 18xx), this is true. On the 12- or 14-bit PICs, there is no instruction to branch based upon the contents of a bit of W.


    #7
    Guest
    Super Member
    • Total Posts : 80503
    • Reward points : 0
    • Joined: 2003/01/01 00:00:00
    • Location: 0
    • Status: online
    Parity challenge 2002/09/16 12:39:00 (permalink)
    0

    Yes, I returned to say that.

    I was thinking about PIC18F...



    Anyway, is the last finishing move possible to be done with SUBLW instruction???

    (subtract W from literal)



    One may use the DC carry instead of a C carry.



    Mario.
    #8
    supercat
    Starting Member
    • Total Posts : 43
    • Reward points : 0
    • Joined: 2003/11/07 12:36:47
    • Status: offline
    Parity challenge 2002/09/17 12:24:00 (permalink)
    0

    Depending upon what the parity is needed for, a possible improvement would be to replace the last "ADDLW" with an "ANDLW'. This will return the parity status in the Z flag, but more notably will leave it in W.7 with the rest of W blank. If the purpose of generating the parity bit was to convert 8-bit outgoing data to even parity, then following an ANDLW an XORWF with the original data will yield a data byte (in W or the register) with even parity, without need for any conditional instructions(!)


    #9
    maxwell
    Super Member
    • Total Posts : 1510
    • Reward points : 0
    • Joined: 2003/11/07 12:35:27
    • Status: offline
    Parity challenge 2002/11/25 14:17:36 (permalink)
    0

    I thought that the carry from B1 into B6 after adding 0x41 somehow worked out right. Let's see:



    Start with 1111 1111 after the XOR.

    Add 0x41; result is 0100 0000 (0x40)

    Now OR 0x7C; result is 0111 1100

    Add 0x02; result is 0111 1110 with no carry



    The MSB is 0, indicating even parity, which is correct.



    John N. Power


    POWER TECHNOLOGIES


    #10
    ric
    Super Member
    • Total Posts : 29935
    • Reward points : 0
    • Joined: 2003/11/07 12:41:26
    • Location: Australia, Melbourne
    • Status: offline
    Parity challenge 2002/11/25 15:05:36 (permalink)
    0

    On 11/25/2002 3:33:06 AM, Simon Wilton wrote:

    >After doing some analysis and

    >testing, the 6 cycle version

    >of the algorithm is pared

    >beyond the bone. It works for

    >most values, but fails for

    >some.

    >[---snip---]

    >Simon



    Hi Simon,

    Which "some" values specifically?


    As I said back on Nov-13, I tested the 6 cycle version on all values from 00 to FF, and it worked for all of them.

    (I was originally worried about unwanted carries propagating through W, which is why I did the brute force test.)
    -Ric

    #11
    Jump to:
    © 2021 APG vNext Commercial Version 4.5