Skip to content

Instantly share code, notes, and snippets.

@NT7S NT7S/compile.txt
Last active Sep 29, 2015

Embed
What would you like to do?
JT65 Encoder in C
gcc jt65_encode.c encode_rs_int.c init_rs_int.c -o jt65_encode
/* 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;
}
}
/* 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"
}
/* 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:;
}
/* 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;
}
/* 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)
#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;
}
/* 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.