!pr0
!lm12
!rm75
Generating Parity..........................Bob Sander-Cederlof

When large amounts of data are being moved around it is easy to garble some.  When you transmit characters over the telephone, or read them from a tape or disk, you want some kind of assurance that the message does not get modified by the medium.

Lots of schemes have been invented to prevent, detect, and even correct transmission errors:  checksums, parity, cyclic redundancy codes, and more.

Checksums are used inside the Apple all the time.  If you ever used cassette tapes with your Apple, you were re-assured to know that each program was recorded with a checksum.  DOS 3.3 adds a checksum to the end of every sector on the disk.  The checksum is re-computed when you read a tape or disk sector; if the result is different, at least one bit in the data is wrong.

Most of the checksums I have seen are of the exclusive-or type.  All the bytes in the data record are EORed together, and the result is written at the end of the record.  When the data is read, the in-coming bytes are again EORed together, and finally EORed with the checksum itself.  If the final result is non-zero, an error occurred.

Checksums in the Apple are usually one byte wide.  However, for more security, you could form a wider checksum.  Or you could ADD the bytes together and store a two byte sum.  Or store the complement of the sum, so that adding all the bytes plus the complement will give a zero result if there are no errors.  [Checksums may check out OK even though errors occur, if the errors are sneaky enough to cancel each other out.]

Parity is really a kind of checksum, but only one bit wide.  A series of bits is EORed together, and the single-bit result is the parity value.  In an ASCII character there is provision for the leading bit position to be used for storing a parity bit.  An eight-bit byte holds seven data bits plus a parity bit.

There are two kinds of parity in use:  even and odd.  Even parity makes the total number of 1-bits in the stream of bits even; odd parity makes the total number of 1-bits odd.  Both even and odd are in use today in various kinds of equipment.  Many terminals and serial communication boards allow you to select even, odd, or no parity.  Looking at the ASCII code for a couple of letters, each could be transmitted in four ways:

Letter "M"  0 1 0 0 1 1 0 1 -- No parity, 8th bit always 0
            1 1 0 0 1 1 0 1 -- No parity, 8th bit always 1
            0 1 0 0 1 1 0 1 -- Even parity
            1 1 0 0 1 1 0 1 -- Odd parity

Letter "Q"  0 1 0 1 0 0 0 1 -- No parity, 8th bit always 0
            1 1 0 1 0 0 0 1 -- No parity, 8th bit always 1
            1 1 0 1 0 0 0 1 -- Even parity
            0 1 0 1 0 0 0 1 -- Odd parity
!np
Sometimes I have needed a quick way to generate or verify a parity bit with software.  These matters are usually handled in hardware, but not always.

In the 6502, it is a very simple matter to rotate a byte around and count the number of one bits present.  Then the parity bit can be merged with the byte, or compared with what is already there.

The following subroutine (PARITY) computes the parity bit and merges it with the data byte.  Call PARITY with the character to be merged in the A-register.  Only the seven data bits will be counted.  As written, the subroutine computes an odd parity bit.  You can change line 1030 to "LDX #0" to compute even parity.

!lm+5
1000 *-------------------------------
1010 *   Compute and merge parity bit
1020 *-------------------------------
1030 PARITY LDX #1     (#0 FOR EVEN PARITY)
1040        ASL        SHIFT PARITY POSITION OUT
1050        PHA        SAVE SHIFTED CHARACTER
1060 .1     BPL .2     IF NEXT BIT = 0, DON'T COUNT
1070        INX        IF NEXT BIT = 1, COUNT IT
1080 .2     ASL        SHIFT IN NEXT BIT
1090        BNE .1     IF ANY REMAINING BITS = 1
1100        TXA        GET COUNT OF 1-BITS
1110        LSR        EVEN/ODD BIT OF COUNT INTO CARRY
1120        PLA        ORIGINAL CHAR BUT SHIFTED
1130        ROR        SHIFT PARITY BIT INTO BIT 8
1140        RTS
!lm-5

I wrote a little program to drive the PARITY subroutine, using all possible values from 0 through 127, and print out the results:

!lm+5
1150 *-------------------------------
1160 PRHEX  .EQ $FDDA  MONITOR PRINT (A) IN HEX
1170 COUT   .EQ $FDED  MONITOR PRINT CHAR IN (A)
1180 *-------------------------------
1190 DEMO   LDA #0     FOR CHAR = $00 TO $7F
1200        STA CHAR
1210 .1     JSR PARITY CALL THE PARITY SUBROUTINE
1220        JSR PRHEX  PRINT THE CHARACTER
1230        INC CHAR   NEXT CHAR
1240        LDA CHAR   SEE IF TIME FOR A NEW LINT
1250        AND #$07
1260        BEQ .2     YES
1270        LDA #$A0   <SPACE>
1280        BNE .3     ...ALWAYS
1290 .2     LDA #$8D   <RETURN>
1300 .3     JSR COUT   PRINT SPACE OR RETURN
1310        LDA CHAR
1320        BPL .1     STILL LESS THAN $80
1330        RTS        DEMO FINISHED
!lm-5
!np
When I set it up for odd parity, here is part of the table printed out by DEMO:

!lm+5
80 01 02 83 04 85 86 07
08 89 8A 0B 8C 0D 0E 8F
10 91 92 13 94 15 16 97
   .
   .
   .

F8 79 7A FB 7C FD FE 7F
!lm-5

Now, how about a subroutine to check parity?  Here is a version that checks an 8-bit value for odd parity.  Simply change line 1420 to "LDX #0" to check for even parity instead.  The subroutine returns with CARRY CLEAR for good parity, or CARRY SET for bad parity.

!lm+5
1400 *-----------------------------
1410 CHECK.PARITY
1420        LDX #1     (OR #0 FOR EVEN PARITY)
1430        PHA        SAVE ORIGINAL CHAR
1440 .1     ASL        SHIFT NEXT BIT INTO CARRY
1450        BEQ .2     NO REMAINING 1-BITS
1460        BCC .1     LEADING BIT NOT 1-BIT
1470        INX        COUNT THE 1-BIT
1480        BCS .1     ...ALWAYS
1490 .2     BCC .3     LATEST SHIFTED BIT WAS 0
1500        INX        LATEST SHIFTED BIT WAS 1
1510 .3     TXA        BIT COUNT
1520        LSR        SHIFT EVEN/ODD BIT INTO CARRY
1530        PLA        RESTORE ORIGINAL CHARACTER
1540        RTS
!lm-5

