\n"; echo " Coding Theory - PHP Script for Binary Linear Error Correcting Codes
\n\n"; ################################################################################ # Set Up ################################################################################ /* $matrix[] = array with following values/subarrays: (1) $code_type = 'hamming,golay,extended golay,etc' (2) $code_n = length of code (3) $code_k = dimension of code (4) $code_d = distance of code, if known (5) $generator[$i] = $i'th row of generator matrix (6) $parity[$i] = $i'th row of parity check matrix (7) $code_original = original message (8) $code_encoded = encoded message (9) $code_decoded = decoded message (10) $code_error_pos[$i] = position of $i'th error (11) $decoded_message = final decoded message I do this all in one array because I'm going to be passing this thing like mad to several functions. */ ################################################################################ # Functions ################################################################################ // need to define a function to chop string into smaller strings for use in coding // this function will be available in PHP5 ... soon to be available. // this function will be used in the 'hamming_encode()' and 'hamming_decode()' functions if (!function_exists('str_split')) { Function str_split($string, $chunksize=1) { preg_match_all('/('.str_repeat('.', $chunksize).')/Uims', $string, $matches); return $matches[1]; } } function make_hamming_parity($matrix,$r) { // creates Hamming parity matrix, given r // create the parity check matrix // Here, I define the parity check matrix for r=2. // The parity check matrix for any r > 2 is recursively generated. $matrix['p_row1'] = array(1,1); $matrix['p_row2'] = array(1,0); $matrix['p_row3'] = array(0,1); $parity_num_rows = 3; // the current parity matrix has this many rows $parity_num_cols = 2; // the current parity matrix has this many columns // Now is the recursive parity check generation algorithm // Do this portion over and over until desired matrix is obtained // --------------------------------------------------------------------------- for($x=3;$x<=$r;$x++) { // (1) copy the first ($parity_num_rows)-($parity_num_cols) rows of the current parity matrix and add on to bottom of matrix $copy_row_source_max = ($parity_num_rows - $parity_num_cols); // calculate the final source row to be copied for($i=1;$i<=$copy_row_source_max;$i++) { $j = $parity_num_rows + $i; $destination_row = "p_row$j"; $source_row = "p_row$i"; $matrix[$destination_row] = $matrix[$source_row]; } // (2) add a '1' to beginning of each row from row 1 to row '$parity_num_rows' $pad_length = -($parity_num_cols + 1); for($i=1;$i<=$parity_num_rows;$i++) { $destination_row = "p_row$i"; $matrix[$destination_row] = array_pad($matrix[$destination_row], $pad_length, 1); } // (3) add a '0' to beginning of each row from row '$parity_num_rows + 1' to '$parity_num_rows + $copy_row_source_max' for($i=1;$i<=$copy_row_source_max;$i++) { $j = $parity_num_rows + $i; $destination_row = "p_row$j"; $matrix[$destination_row] = array_pad($matrix[$destination_row], $pad_length, 0); } // (4) add the '$parity_num_cols + 1' identity matrix on to the bottom $parity_num_cols++; // the col dimension of the new parity check matrix $j = ($parity_num_rows + $copy_row_source_max); $parity_num_rows = ($j + $parity_num_cols); // the row dimension of the new parity check matrix $j++; for($i=1;$i<=$parity_num_cols;$i++) { $destination_row = "p_row$j"; $matrix[$destination_row] = array(); for($k=1;$k<=$parity_num_cols;$k++) { if ($k == $i) $matrix[$destination_row][] = "1"; else $matrix[$destination_row][] = "0"; } $j++; } } // --------------------------------------------------------------------------- return $matrix; } // function to make hamming generator matrix when given hamming parity matrix function make_hamming_generator($matrix,$r) { // input $matrix with parity rows and input $r (col dimension) of parity matrix // copy all of parity check matrix except the identity rows at the bottom // the parity check matrix is (2^r)-1 rows long -> copy first '(2^r)-1-r' rows $copy_row_source_max = pow(2,$r)-1-$r; $generator_num_col = -($copy_row_source_max + $r); for($i=1;$i<=$copy_row_source_max;$i++) { $destination_row = "g_row$i"; $source_row = "p_row$i"; $matrix[$destination_row] = $matrix[$source_row]; $matrix[$destination_row] = array_pad($matrix[$destination_row], $generator_num_col, 0); $index = $i-1; $matrix[$destination_row][$index] = 1; } return $matrix; } // need a function to print matrix rows recursively for output display function print_matrix($matrix,$index) { // print hamming matrix $hamming over index $index (p_row -> parity, g_row -> generator) echo "
![\"\"](\"matrix_images/matrix_left.gif\") | \n";
$k=1; $l=0; while ($k==1) {
$source_col = $l;
if (array_key_exists($source_col, $matrix[$source_row])) echo " " . $matrix[$source_row][$source_col] . " | \n"; else $k=0; $l++; } echo "![\"\"](\"matrix_images/matrix_right.gif\") |
\n"; } // need to define function for multiplication of a vector and a matrix function vector_x_matrix($vector,$hamming,$index) { // index is the row index of the matrix ('p_row' for parity, 'g_row' for generator) $vector_components = str_split($vector,1); // split each word into component parts, one bit per part $matrix_height = count($vector_components); // how many bits are in the word $codeword = ""; // set codeword to null // $message length = vector size = matrix y dimension // get the size of matrix x dimension $row_source = $index . "1"; $i=0; while($i>=0) { if(isset($hamming[$row_source][$i])) $matrix_width = $i+1; else $i=-2; $i++; } $codeword=""; for($i=1;$i<=$matrix_width;$i++) { // iterate through the generator matrix by column $sum=0; for($j=1;$j<=$matrix_height;$j++) { // iterate through the generator matrix (and word) by row (by column) $row = $index . "$j"; // declare row in generator matrix $word_pos = $j-1; // declare position in word $row_pos = $i-1; // declare row position in matrix if (($hamming[$row][$row_pos] == 1) && ($vector_components[$word_pos] == 1)) $product=1; else $product=0; if ($product == 1) if ($sum == 1) $sum=0; else $sum=1; // the sum will only change if the product is 1 } $codeword .= $sum; } return $codeword; } function hamming_encode($code_length,$message,$hamming) { // given $code_length, $hamming (matrix), and $message -> generate coded message // break the message in to codes of length $code_length $code = str_split($message,$code_length); $codeword = ""; $index = "g_row"; // set index to g_row for multiplication with generator matrix $num_words = count($code); for($i=0;$i<$num_words;$i++) { $string = $code[$i]; $codeword .= vector_x_matrix($string,$hamming,$index); } // multiply each vector in the $code array by the generator hamming matrix ($hamming['g_row'][0-$code_length]) return $codeword; } function hamming_decode($code_length,$r,$decode_mode,$message,$hamming) { // given $code_length, $hamming (matrix), and $message -> decode coded message // break the message in to codes of length $code_length $code = str_split($message,$code_length); $codeword = ""; $index = "p_row"; // set index to p_row for multiplication with parity check matrix $num_words = count($code); if ($decode_mode == "0") $dimension = pow(2,$r)-1-$r; else $dimension = $code_length; for($i=0;$i<$num_words;$i++) { $string = $code[$i]; $syndrome = vector_x_matrix($string,$hamming,$index); // this returns the syndrome // figure out which syndrome we have, or if we have the 0 row -> correct error and bolden correction if (!eregi("[^0]",$syndrome)) $codeword .= $code[$i]; // no errors in this codeword else { $syndrome_split = str_split($syndrome,1); for($j=0;$j<$code_length;$j++) { // cycle through rows of parity check matrix until a match is found $parity_row = $j+1; $parity_row = $index . $parity_row; if ($syndrome_split == $hamming[$parity_row]) { // the error is located at site $j // change the '$j'th location of $string, add html bold chars $string_split = str_split($string,1); if ($string_split[$j] == 1) $string_split[$j] = "0"; else $string_split[$j] = "1"; } } for($j=0;$j<$dimension;$j++) $codeword .= $string_split[$j]; } // endelse } // endfor return $codeword; } ################################################################################ # End of Functions / Begin Dynamic Page Display ################################################################################ // unset errors - build error array. unset($errors); ################################################################################ # Hamming Pages ################################################################################ // Error checking on input if ($code_type == "hamming") { // error checking // unset errors unset($errors); if ($action == "declare"); // The only variables currently passed for this option are hard coded and consistent. if ($action == "submit") { // Encoding/Decoding Hamming Codes if ($duty == "encode") { // Variables passed consistent: $code_type=hamming, $r=r, $duty=encode // Variables passed possible error: $message=010...01010; // For a Hamming code, messages are of length "pow(2,$r)-1-$r" $message = eregi_replace("[^01]","",$message); if (eregi("[^01]",$message)) $errors .= "Only the chars 0 and 1 are allowed in binary codes. Please modify your message.
\n"; $message_len = strlen($message); $code_length = pow(2,$r)-1-$r; if (($message_len % $code_length) != 0) $errors .= "This Hamming code encodes messages of length $code_length. Please modify your message.
All chars besides 0 and 1 have been removed.
\n"; } elseif ($duty == "decode") { // Variables passed consistent: $code_type=hamming, $r=r, $duty=decode // Variables passed possible error: $message=010...01010; // For a Hamming code, messages are of length "pow(2,$r)-1" $message = eregi_replace("[^01]","",$message); if (eregi("[^01]",$message)) $errors .= "Only the chars 0 and 1 are allowed in binary codes. Please modify your message.
\n"; $message_len = strlen($message); $code_length = pow(2,$r)-1; if (($message_len % $code_length) != 0) $errors .= "This Hamming code decodes messages of length $code_length. Please modify your message.
All chars besides 0 and 1 have been removed.
\n"; } else $errors .= "There was an error performing that operation. Please try again.
\n"; } } // first Hamming view // VARIABLES: $action=declare, $code_type=hamming, $r=r if ((($action == "declare") || (isset($errors))) && ($code_type == "hamming")) { $matrix = array(); $matrix['code_type'] = "hamming"; $matrix['code_n'] = pow(2,$r)-1; $matrix['code_k'] = pow(2,$r)-1-$r; $matrix['code_d'] = 3; echo "
You have chosen to use the " . $matrix['code_type'] . " code with parameters (" . $matrix['code_n'] . "," . $matrix['code_k'] . "," . $matrix['code_d'] . ").
\n"; // create the parity check matrix and generator matrix for this code // since I create the generator from the parity check matrix, we'll make the parity check matrix first $matrix = make_hamming_parity($matrix,$r); $matrix = make_hamming_generator($matrix,$r); echo "A generator matrix G for this code is a " . $matrix['code_k'] . " by " . $matrix['code_n'] . " matrix where:
\n"; echo "![\"\"](\"e.gif\") G = | "; $index = "g_row"; print_matrix($matrix,$index); echo " |
And, a parity check matrix P for this code is a " . $matrix['code_n'] . " by " . $r . " matrix where:
\n"; echo "P = | "; $index = "p_row"; print_matrix($matrix,$index); echo " |
$errors
\n"; else echo "\n"; echo "
To encode or decode a message with this Hamming code, please use the following form:\n"; echo " \n"; echo "
Return to the main linear codes page here.
\n"; } elseif ((($action == "submit") && (!isset($errors))) && ($code_type == "hamming")) { $matrix = array(); $matrix['code_type'] = "hamming"; $matrix['code_n'] = pow(2,$r)-1; $matrix['code_k'] = pow(2,$r)-1-$r; $matrix['code_d'] = 3; echo "You have chosen to $duty a message using a " . $matrix['code_type'] . " code with parameters (" . $matrix['code_n'] . "," . $matrix['code_k'] . "," . $matrix['code_d'] . ").
\n"; // create the parity check matrix and generator matrix for this code // since I create the generator from the parity check matrix, we'll make the parity check matrix first $matrix = make_hamming_parity($matrix,$r); $matrix = make_hamming_generator($matrix,$r); if ($duty == "encode") { echo "The generator matrix G used to encode the message is a " . $matrix['code_k'] . " by " . $matrix['code_n'] . " matrix where:
\n"; echo "G = | "; $index = "g_row"; print_matrix($matrix,$index); echo " |
| The original message: | \n"; echo "";
if ($message_rows > 0) for($i=0;$i<$message_rows;$i++) {
echo $message_split[$i];
if (((($i+1)%60)==0)) echo "\n "; } echo " |
| The encoded message: | \n"; echo "";
if ($message_coded_rows > 0) for($i=0;$i<$message_coded_rows;$i++) {
echo $message_coded_split[$i];
if (((($i+1)%60)==0)) echo "\n "; } echo " |
\n"; echo "
To encode or decode a message with this Hamming code, please use the following form:
(The codeword just encoded is inserted in the textarea. Hit submit to decode.)
(You may also change one digit per codeword for error correction in decoding.)\n"; echo " \n"; } else { echo "
The parity check matrix P used to decode the message is a " . $matrix['code_n'] . " by " . $r . " matrix where:
\n"; echo "P = | "; $index = "p_row"; print_matrix($matrix,$index); echo " |
| The received message: | \n"; echo "";
if ($message_rows > 0) for($i=0;$i<$message_rows;$i++) {
echo $message_split[$i];
if (((($i+1)%60)==0)) echo "\n "; } echo " |
| Error corrections are in bold if they exist. | |
| The error corrected message: | \n"; echo "";
reset($message_coded_split);
$i=-1; $j=1;
while($j>0) {
if (!eregi("[^01]",current($message_coded_split))) $i++;
echo current($message_coded_split);
if (((($i+1)%60)==0)) echo "\n "; if (next($message_coded_split) > -1); else $j=0; } $message_corrected = eregi_replace("","",$message_corrected); $message_corrected = eregi_replace("","",$message_corrected); $message_decoded = str_split($message_corrected,1); echo " |
| The decoded message: | \n"; echo "";
// $matrix['code_n'] = length of code word
// $matrix['code_d'] = lenfth of message word
$message_rows = count($message_decoded); $j=0;
unset($message_original);
if ($message_rows > 0) for($i=0;$i<$message_rows;$i++) {
$k=$i;
if ((($k)%$matrix['code_n'])<$matrix['code_k']) { echo $message_decoded[$i]; $message_original .= $message_decoded[$i]; $j++; }
if (((($j+1)%60)==0)) echo "\n "; } echo " |
\n"; echo "
To encode or decode a message with this Hamming code, please use the following form:
(The codeword just decoded is inserted in the textarea. Hit submit to encode.)\n"; echo " \n"; } echo "
Return to the main linear codes page here.
\n"; } ################################################################################ # Main Page - First view ################################################################################ if ((!isset($action)) || (empty($action))) { // first view echo "\n
Please select the type of code you wish to use for message encoding/decoding.
\n\n"; echo "| Hamming | \n"; echo "(3,1,3) | \n"; echo "(7,4,3) | \n"; echo "(15,11,3) | \n"; echo "(31,26,3) | \n"; echo "(63,57,3) | \n"; echo "(127,120,3) | \n"; echo "(255,247,3) | \n"; echo "
These binary linear error correcting codes are expressed in terms of (n,k,d), where:\n";
echo "n = length of each codeword.\n";
echo "k = dimension of each codeword. Thus, n-k is the number of parity check or redundant bits.\n";
echo "d = minimum distance between any two codewords.\n";
}
################################################################################
# Import Footer // HTML portion
################################################################################
echo "