JT65 Encoder in C

compile.txt

gcc jt65_encode.c encode_rs_int.c init_rs_int.c -o jt65_encode

encode_rs.h

/* The guts of the Reed-Solomon encoder, meant to be #included
 * into a function body with the following typedefs, macros and variables supplied
 * according to the code parameters:

 * data_t - a typedef for the data symbol
 * data_t data[] - array of NN-NROOTS-PAD and type data_t to be encoded
 * data_t parity[] - an array of NROOTS and type data_t to be written with parity symbols
 * NROOTS - the number of roots in the RS code generator polynomial,
 *          which is the same as the number of parity symbols in a block.
            Integer variable or literal.
	    * 
 * NN - the total number of symbols in a RS block. Integer variable or literal.
 * PAD - the number of pad symbols in a block. Integer variable or literal.
 * ALPHA_TO - The address of an array of NN elements to convert Galois field
 *            elements in index (log) form to polynomial form. Read only.
 * INDEX_OF - The address of an array of NN elements to convert Galois field
 *            elements in polynomial form to index (log) form. Read only.
 * MODNN - a function to reduce its argument modulo NN. May be inline or a macro.
 * GENPOLY - an array of NROOTS+1 elements containing the generator polynomial in index form

 * The memset() and memmove() functions are used. The appropriate header
 * file declaring these functions (usually <string.h>) must be included by the calling
 * program.

 * Copyright 2004, Phil Karn, KA9Q
 * May be used under the terms of the GNU Lesser General Public License (LGPL)
 */


#undef A0
#define A0 (NN) /* Special reserved value encoding zero in index form */

{
  int i, j;
  data_t feedback;

  memset(parity,0,NROOTS*sizeof(data_t));

  for(i=0;i<NN-NROOTS-PAD;i++){
    feedback = INDEX_OF[data[i] ^ parity[0]];
    if(feedback != A0){      /* feedback term is non-zero */
#ifdef UNNORMALIZED
      /* This line is unnecessary when GENPOLY[NROOTS] is unity, as it must
       * always be for the polynomials constructed by init_rs()
       */
      feedback = MODNN(NN - GENPOLY[NROOTS] + feedback);
#endif
      for(j=1;j<NROOTS;j++)
	parity[j] ^= ALPHA_TO[MODNN(feedback + GENPOLY[NROOTS-j])];
    }
    /* Shift */
    memmove(&parity[0],&parity[1],sizeof(data_t)*(NROOTS-1));
    if(feedback != A0)
      parity[NROOTS-1] = ALPHA_TO[MODNN(feedback + GENPOLY[0])];
    else
      parity[NROOTS-1] = 0;
  }
}

encode_rs_int.c

/* Reed-Solomon encoder
 * Copyright 2003, Phil Karn, KA9Q
 * May be used under the terms of the GNU Lesser General Public License (LGPL)
 */
#include <string.h>

#include "int.h"
#include "rs-common.h"

void encode_rs_int(void *p,data_t *data, data_t *parity){
  struct rs *rs = (struct rs *)p;

#include "encode_rs.h"

}

init_rs.h

/* Common code for intializing a Reed-Solomon control block (char or int symbols)
 * Copyright 2004 Phil Karn, KA9Q
 * May be used under the terms of the GNU Lesser General Public License (LGPL)
 */
#undef NULL
#define NULL ((void *)0)

{
  int i, j, sr,root,iprim;

  rs = NULL;
  /* Check parameter ranges */
  if(symsize < 0 || symsize > 8*sizeof(data_t)){
    goto done;
  }

  if(fcr < 0 || fcr >= (1<<symsize))
    goto done;
  if(prim <= 0 || prim >= (1<<symsize))
    goto done;
  if(nroots < 0 || nroots >= (1<<symsize))
    goto done; /* Can't have more roots than symbol values! */
  if(pad < 0 || pad >= ((1<<symsize) -1 - nroots))
    goto done; /* Too much padding */

  rs = (struct rs *)calloc(1,sizeof(struct rs));
  if(rs == NULL)
    goto done;

  rs->mm = symsize;
  rs->nn = (1<<symsize)-1;
  rs->pad = pad;

  rs->alpha_to = (data_t *)malloc(sizeof(data_t)*(rs->nn+1));
  if(rs->alpha_to == NULL){
    free(rs);
    rs = NULL;
    goto done;
  }
  rs->index_of = (data_t *)malloc(sizeof(data_t)*(rs->nn+1));
  if(rs->index_of == NULL){
    free(rs->alpha_to);
    free(rs);
    rs = NULL;
    goto done;
  }

  /* Generate Galois field lookup tables */
  rs->index_of[0] = A0; /* log(zero) = -inf */
  rs->alpha_to[A0] = 0; /* alpha**-inf = 0 */
  sr = 1;
  for(i=0;i<rs->nn;i++){
    rs->index_of[sr] = i;
    rs->alpha_to[i] = sr;
    sr <<= 1;
    if(sr & (1<<symsize))
      sr ^= gfpoly;
    sr &= rs->nn;
  }
  if(sr != 1){
    /* field generator polynomial is not primitive! */
    free(rs->alpha_to);
    free(rs->index_of);
    free(rs);
    rs = NULL;
    goto done;
  }

  /* Form RS code generator polynomial from its roots */
  rs->genpoly = (data_t *)malloc(sizeof(data_t)*(nroots+1));
  if(rs->genpoly == NULL){
    free(rs->alpha_to);
    free(rs->index_of);
    free(rs);
    rs = NULL;
    goto done;
  }
  rs->fcr = fcr;
  rs->prim = prim;
  rs->nroots = nroots;

  /* Find prim-th root of 1, used in decoding */
  for(iprim=1;(iprim % prim) != 0;iprim += rs->nn)
    ;
  rs->iprim = iprim / prim;

  rs->genpoly[0] = 1;
  for (i = 0,root=fcr*prim; i < nroots; i++,root += prim) {
    rs->genpoly[i+1] = 1;

    /* Multiply rs->genpoly[] by  @**(root + x) */
    for (j = i; j > 0; j--){
      if (rs->genpoly[j] != 0)
	rs->genpoly[j] = rs->genpoly[j-1] ^ rs->alpha_to[modnn(rs,rs->index_of[rs->genpoly[j]] + root)];
      else
	rs->genpoly[j] = rs->genpoly[j-1];
    }
    /* rs->genpoly[0] can never be zero */
    rs->genpoly[0] = rs->alpha_to[modnn(rs,rs->index_of[rs->genpoly[0]] + root)];
  }
  /* convert rs->genpoly[] to index form for quicker encoding */
  for (i = 0; i <= nroots; i++)
    rs->genpoly[i] = rs->index_of[rs->genpoly[i]];
 done:;

}

init_rs_int.c

/* Initialize a RS codec
 *
 * Copyright 2002 Phil Karn, KA9Q
 * May be used under the terms of the GNU Lesser General Public License (LGPL)
 */
#include <stdlib.h>

#include "int.h"
#include "rs-common.h"

void free_rs_int(void *p){
  struct rs *rs = (struct rs *)p;

  free(rs->alpha_to);
  free(rs->index_of);
  free(rs->genpoly);
  free(rs);
}

/* Initialize a Reed-Solomon codec
 * symsize = symbol size, bits
 * gfpoly = Field generator polynomial coefficients
 * fcr = first root of RS code generator polynomial, index form
 * prim = primitive element to generate polynomial roots
 * nroots = RS code generator polynomial degree (number of roots)
 * pad = padding bytes at front of shortened block
 */
void *init_rs_int(int symsize,int gfpoly,int fcr,int prim,
	int nroots,int pad){
  struct rs *rs;

#include "init_rs.h"

  return rs;
}

int.h

/* Stuff specific to the general (integer) version of the Reed-Solomon codecs
 *
 * Copyright 2003, Phil Karn, KA9Q
 * May be used under the terms of the GNU Lesser General Public License (LGPL)
 */
typedef unsigned int data_t;

#define MODNN(x) modnn(rs,x)

#define MM (rs->mm)
#define NN (rs->nn)
#define ALPHA_TO (rs->alpha_to) 
#define INDEX_OF (rs->index_of)
#define GENPOLY (rs->genpoly)
#define NROOTS (rs->nroots)
#define FCR (rs->fcr)
#define PRIM (rs->prim)
#define IPRIM (rs->iprim)
#define PAD (rs->pad)
#define A0 (NN)

jt65_encode.c

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <ctype.h>
#include "rs-common.h"

static void * rs;

uint8_t jt_code(char c)
{
	/* Validate the input then return the proper integer code */
	// Return 255 as an error code if the char is not allowed

	if(isdigit(c))
	{
		return (uint8_t)(c - 48);
	}
	else if(c >= 'A' && c <= 'Z')
	{
		return (uint8_t)(c - 55);
	}
	else if(c == ' ')
	{
		return 36;
	}
	else if(c == '+')
	{
		return 37;
	}
	else if(c == '-')
	{
		return 38;
	}
	else if(c == '.')
	{
		return 39;
	}
	else if(c == '/')
	{
		return 40;
	}
	else if(c == '?')
	{
		return 41;
	}
	else
	{
		return 255;
	}
}

uint8_t gray_code(uint8_t c)
{
	return (c >> 1) ^ c;
}

void rs_encode(uint8_t * data, uint8_t * symbols)
{
  int dat1[12];
  int b[51];
  int i;

  // Reverse data order for the Karn codec.
  for(i = 0; i < 12; i++)
  {
    dat1[i] = data[11 - i];
  }
  // Compute the parity symbols
  encode_rs_int(rs, dat1, b);

  // Move parity symbols and data into symbols array, in reverse order.
  for (i = 0; i < 51; i++)
  {
  	symbols[50-i] = b[i];
  }
  
  for (i = 0; i < 12; i++)
  {
  	symbols[i + 51] = dat1[11 - i];
  }
}

int main(int argc, char *argv[])
{
	uint8_t i, j;
  char message[14] = "NT7S CN85";
  
  // Initialize the Reed-Solomon encoder
  rs = (struct rs *)(intptr_t)init_rs_int(6, 0x43, 3, 1, 51, 0);
		
	// Convert all chars to uppercase
	
	// Collapse multiple spaces down to one
	
	// Pad the message with trailing spaces

	uint8_t len = strlen(message);
	if(len < 13)
	{
		for(i = len; i < 13; i++)
		{
			message[i] = ' ';
		}
	}
	
	// Print the message
	printf("Message:\n   %s\n\n", message);
	
	// Bit packing
	// -----------
	uint8_t c[13];
	uint32_t n1, n2, n3;
	
	// Find the N values
	n1 = jt_code(message[0]);
	n1 = n1 * 42 + jt_code(message[1]);
	n1 = n1 * 42 + jt_code(message[2]);
	n1 = n1 * 42 + jt_code(message[3]);
	n1 = n1 * 42 + jt_code(message[4]);
	
	n2 = jt_code(message[5]);
	n2 = n2 * 42 + jt_code(message[6]);
	n2 = n2 * 42 + jt_code(message[7]);
	n2 = n2 * 42 + jt_code(message[8]);
	n2 = n2 * 42 + jt_code(message[9]);
	
	n3 = jt_code(message[10]);
	n3 = n3 * 42 + jt_code(message[11]);
	n3 = n3 * 42 + jt_code(message[12]);
	
	
	// Pack bits 15 and 16 of N3 into N1 and N2,
	// then mask reset of N3 bits
	n1 = (n1 << 1) + ((n3 >> 15) & 1);
	n2 = (n2 << 1) + ((n3 >> 16) & 1);
	n3 = n3 & 0x7fff;
	
	// Set the freeform message flag
	n3 += 32768;
	
	c[0] = (n1 >> 22) & 0x003f;
	c[1] = (n1 >> 16) & 0x003f;
	c[2] = (n1 >> 10) & 0x003f;
	c[3] = (n1 >> 4) & 0x003f;
	c[4] = ((n1 & 0x000f) << 2) + ((n2 >> 26) & 0x0003);
	c[5] = (n2 >> 20) & 0x003f;
	c[6] = (n2 >> 14) & 0x003f;
	c[7] = (n2 >> 8) & 0x003f;
	c[8] = (n2 >> 2) & 0x003f;
	c[9] = ((n2 & 0x0003) << 4) + ((n3 >> 12) & 0x000f);
	c[10] = (n3 >> 6) & 0x003f;
	c[11] = n3 & 0x003f;
	
	//printf("N2: %x\n", n2);
	//printf("N3: %x\n\n", n3);
	
	// Print the 12 6-bit symbols for debugging
	printf("Packed message, 6-bit symbols:\n  ");
	for(i = 0; i < 12; i++)
	{
		printf("%3u", c[i]);
	}
	printf("\n\n");

	
	// Reed-Solomon encoding
	// ---------------------
	uint8_t s[63];
	uint8_t k = 0;
	
	rs_encode(c, s);
	
	printf("Reed-Solomon Encoding:\n");
	for(i = 0; i < 3; i++)
	{
		printf("  ");
		for(j = 0; j < 21; j++)
		{
			printf("%3u", s[k]);
			k++;
		}
		printf("\n");
	}

	/*
	// Interleaving
	// ------------
	uint8_t d[63];
	uint8_t d1[7][9], d2[9][7];
	
	// Fill temp d1 array
	//     right order???
	for(i = 0; i < 7; i++)
	{
		for(j = 0; j < 9; j++)
		{
			d1[i][j] = s[(j * 7) + i];
		}
	}
	
	// Do the interleaving
	for(i = 0; i < 7; i++)
	{
		for(j = 0; j < 9; j++)
		{
			d2[j][i] = d1[i][j];
		}
	}
	
	// Translate back to 1D destination array
	for(i = 0; i < 7; i++)
	{
		for(j = 0; j < 9; j++)
		{
			d[(j * 7) + i] = d2[i][j];
		}
	}
	
	printf("Interleaving:\n");
	for(i = 0; i < 63; i++)
	{
		printf("%u ", d[i]);
	}
	printf("\n\n");
	
	// Gray Code
	// ---------
	uint8_t g[63];
	
	for(i = 0; i < 63; i++)
	{
		g[i] = gray_code(d[i]);
	}
	
	printf("Gray Code:\n");
	for(i = 0; i < 63; i++)
	{
		printf("%u ", g[i]);
	}
	printf("\n\n");
	*/

  return 0;
}

rs-common.h

/* Stuff common to all the general-purpose Reed-Solomon codecs
 * Copyright 2004 Phil Karn, KA9Q
 * May be used under the terms of the GNU Lesser General Public License (LGPL)
 */

#include "int.h"

/* Reed-Solomon codec control block */
struct rs {
  int mm;              /* Bits per symbol */
  int nn;              /* Symbols per block (= (1<<mm)-1) */
  data_t *alpha_to;     /* log lookup table */
  data_t *index_of;     /* Antilog lookup table */
  data_t *genpoly;      /* Generator polynomial */
  int nroots;     /* Number of generator roots = number of parity symbols */
  int fcr;        /* First consecutive root, index form */
  int prim;       /* Primitive element, index form */
  int iprim;      /* prim-th root of 1, index form */
  int pad;        /* Padding bytes in shortened block */
};

static inline int modnn(struct rs *rs,int x){
  while (x >= rs->nn) {
    x -= rs->nn;
    x = (x >> rs->mm) + (x & rs->nn);
  }
  return x;
}