How to generate CRC table for CRC-6?-CodePudding

I want to create a table for CRC-6/CDMA2000-A. I tried for various CRC-8 and this algo below works fine but for CRC-6 I get arrays which don't work for me. Either the array is wrong or the function I use to calculate CRC-6 with the array.

const POLYNOMIAL = $27;
      BitsCRC = 6;
var Table: array[0..255] of Byte;
    i: Integer;
    j: Integer;
    temp: Byte;
    S: String;
    Mask: Byte;
begin
  mask := (1 shl (BitsCRC - 1));

  for i:=0 to 255 do Table[i] := i ;

  for i:=0 to 255 do begin
        for j:=7 downto 0 do begin
            temp := Table[i] and Mask;

            if (temp <> 0) then begin
                Table[i] := Table[i] shl 1;
                Table[i] := Table[i] xor POLYNOMIAL;
            end
            else begin
                Table[i] := Table[i] shl 1;
            end;
        end;
    end;


  S := '';
  for i:=0 to 255 do begin
    S := S   '$'   IntToHex(Table[i], 2)  ', ';
    if i mod 16 = 15 then begin
      Memo1.Lines.Add(s);
      S := '';
    end;
  end;

I get this array from the code above:

$00, $F5, $CD, $38, $9A, $6F, $57, $A2, $34, $C1, $F9, $0C, $AE, $5B, $63, $96,
$4F, $BA, $82, $77, $D5, $20, $18, $ED, $7B, $8E, $B6, $43, $E1, $14, $2C, $D9,
$9E, $6B, $53, $A6, $04, $F1, $C9, $3C, $AA, $5F, $67, $92, $30, $C5, $FD, $08,
$D1, $24, $1C, $E9, $4B, $BE, $86, $73, $E5, $10, $28, $DD, $7F, $8A, $B2, $47,
$00, $F5, $CD, $38, $9A, $6F, $57, $A2, $34, $C1, $F9, $0C, $AE, $5B, $63, $96,
$4F, $BA, $82, $77, $D5, $20, $18, $ED, $7B, $8E, $B6, $43, $E1, $14, $2C, $D9,
$9E, $6B, $53, $A6, $04, $F1, $C9, $3C, $AA, $5F, $67, $92, $30, $C5, $FD, $08,
$D1, $24, $1C, $E9, $4B, $BE, $86, $73, $E5, $10, $28, $DD, $7F, $8A, $B2, $47,
$00, $F5, $CD, $38, $9A, $6F, $57, $A2, $34, $C1, $F9, $0C, $AE, $5B, $63, $96,
$4F, $BA, $82, $77, $D5, $20, $18, $ED, $7B, $8E, $B6, $43, $E1, $14, $2C, $D9,
$9E, $6B, $53, $A6, $04, $F1, $C9, $3C, $AA, $5F, $67, $92, $30, $C5, $FD, $08,
$D1, $24, $1C, $E9, $4B, $BE, $86, $73, $E5, $10, $28, $DD, $7F, $8A, $B2, $47,
$00, $F5, $CD, $38, $9A, $6F, $57, $A2, $34, $C1, $F9, $0C, $AE, $5B, $63, $96,
$4F, $BA, $82, $77, $D5, $20, $18, $ED, $7B, $8E, $B6, $43, $E1, $14, $2C, $D9,
$9E, $6B, $53, $A6, $04, $F1, $C9, $3C, $AA, $5F, $67, $92, $30, $C5, $FD, $08,
$D1, $24, $1C, $E9, $4B, $BE, $86, $73, $E5, $10, $28, $DD, $7F, $8A, $B2, $47

I try to generate CRC-6 like this:

procedure crc6_update(var CRC: Byte; Str: String);
var i: Integer;
begin
  for i:=1 to Length(Str) do    
       CRC := CRC_Table[(CRC shl 2) xor ord(Str[i]) ] ;
 
end;           

CRC := $3f;
crc6_update(CRC, '123456789');

Caption := IntToHex(CRC, 2);

CodePudding user response：

There are a few problems. You are shifting junk up into the top two bits of the table entries, but then not getting rid of them with an and. More importantly, you are ignoring the top two bits, bits 6 and 7, of each initial table entry (i) with your mask, which is looking at bit 5.

To do this correctly, you need to compute the CRC in the top six bits of the byte (i) being processed. You mask bit 7 instead of bit 5, and you shift the polynomial up two bits to match that. If you are doing this in a byte, then that will take care of the junk being shifted up, since it falls off of the top of the byte.

You want:

Mask := 1 shl 7;

and:

Table[i] := Table[i] xor (POLYNOMIAL shl 2);

Now the CRCs in your table are actually where you'd want them to be anyway, which is in the top six bits of each byte. Then you don't need to do the CRC shl 2 for every single byte you compute. Instead that line in your calculation becomes:

CRC := CRC_Table[CRC xor ord(Str[i])];

Then after your loop you need to shift the CRC down two to return the CRC in the low six bits:

CRC := CRC shr 2;

This will give the correct answer for that test vector, which is $0D.

I am not clear on why you have three loops with an array for your table generation. It seems like it would be simpler to do it like this, with one loop and no array (not tested -- I don't know Pascal/Delphi):

i: Integer;
j: Integer;
crc: Byte;
S: String;
begin
  S := '';
  for i := 0 to 255 do begin
    crc := i;
    for j := 0 to 7 do
      if ((crc and $80) <> 0) then
        crc := (crc shl 1) xor $9c;
      else
        crc := crc shl 1;
    S := S   '$'   IntToHex(crc, 2)   ', ';
    if i mod 16 = 15 then begin
      Memo1.Lines.Add(S);
      S := '';
    end;
  end;
end;