Algorithm-Hamming-Perl
view release on metacpan or search on metacpan
return $output;
}
# unhamming_err - this turns hamming code into data. This has been written
# with memory and CPU efficiencu in mind (without resorting to C).
#
sub unhamming_err {
my $data = shift; # input data
my $pos; # counter to step through data string
my $err; # corrected bit error
my $chars_in; # input bytes
my $ham_text; # hamming code in binary text "0101..", 2 bytes
my $ham_text1; # hamming code for first byte
my $ham_text2; # hamming code for second byte
my $char_out1; # output data byte 1
my $char_out2; # output data byte 2
my $output = ""; # full output data as bytes
my $err_all = 0; # count of corrected bit errors
my $length = length($data);
#
# Step through the $data 3 bytes at a time, decoding it back into
# the $output data.
#
for ($pos = 0; $pos < ($length-2); $pos+=3) {
### Fetch 3 bytes
}
# unhamchar - this takes a hamming code as binary text "0101..." and returns
# both the char and number (0 or 1) to represent if correction
# occured.
#
sub unhamchar {
my $text = shift;
my $pos = 0; # counter
my $err = 0; # error bit position
my ($bit);
### If okay, return now
if (defined $Hamming8rev{$text}) {
return ($Hamming8rev{$text},0);
}
### Find error bit
my $copy = $text;
while ($copy ne "") {
$pos++;
$bit = chop($copy);
if ($bit eq "1") {
$err = $err ^ $pos;
}
}
### Correct error bit
$copy = $text;
if ($err <= 12) {
$bit = substr($copy,-$err,1);
if ($bit eq "0") { $bit = "1"; }
else { $bit = "0"; }
substr($copy,-$err,1) = $bit;
}
### If okay now, return
if (defined $Hamming8rev{$copy}) {
1;
__END__
# Below is stub documentation for your module. You better edit it!
=head1 NAME
Algorithm::Hamming::Perl - Perl implementation of ECC Hamming encoding,
for single bit auto error correction.
=head1 SYNOPSIS
use Algorithm::Hamming::Perl qw(hamming unhamming);
$code = hamming($data); # Encode $data
$data = unhamming($code); # Decode and fix errors
($data,$errors) = unhamming($code); # + return error count
=head1 DESCRIPTION
This is an Error Correction Code module, implementing Hamming encoding
(8 bits data, 4 bits Hamming - ie increases data size by 50%). Data can
be encoded so that single bit errors within a byte are auto-corrected.
This may be useful as a precaution before storing or sending data where
single bit errors are expected.
Hamming encoding was invented by Richard Hamming, Bell Labs, during 1948.
=head1 EXPORT SUBROUTINES
=over 4
=item hamming (SCALAR)
Returns the Hamming code from the provided input data.
=item unhamming (SCALAR)
Returns the original data from the provided Hamming code. Single bit errors
are auto corrected.
=item unhamming_err (SCALAR)
Returns the original data from the provided Hamming code, and a number counting
the number of bytes that were corrected. Single bit errors are auto corrected.
=back
=head1 OTHER SUBROUTINES
=over 4
=item Algorithm::Hamming::Perl::hamming_faster ()
This is an optional subroutine that will speed Hamming encoding if it is
use Algorithm::Hamming::Perl qw(hamming unhamming);
$data = "Hello";
$hamcode = hamming($data);
$original = unhamming($hamcode);
=head1 LIMITATIONS
This is Perl only and can be slow. The Hamming encoding used can only
repair a single bit error within a byte - ie if two bits are damaged within
the one byte then this encoding cannot auto correct the error.
=head1 BUGS
Try not to join Hamming encoded strings together - this may give results
that look like a bug. If an odd number of input byes is encoded, the output
code is short half a byte - and so is padded with '0' bits. Joining these
with a string concatenation will contain the padding bits that will confuse
decoding.
The above problem can occur when inputing and outputing certain lengths
NAME
Algorithm::Hamming::Perl - Perl implementation of ECC
Hamming encoding, for single bit auto error correction.
SYNOPSIS
use Algorithm::Hamming::Perl qw(hamming unhamming);
$code = hamming($data); # Encode $data
$data = unhamming($code); # Decode and fix errors
($data,$errors) = unhamming($code); # + return error count
DESCRIPTION
This is an Error Correction Code module, implementing
Hamming encoding (8 bits data, 4 bits Hamming - ie increases
data size by 50%). Data can be encoded so that single bit
errors within a byte are auto-corrected.
This may be useful as a precaution before storing or sending
data where single bit errors are expected.
Hamming encoding was invented by Richard Hamming, Bell Labs,
during 1948.
EXPORT SUBROUTINES
hamming (SCALAR)
Returns the Hamming code from the provided input data.
unhamming (SCALAR)
Returns the original data from the provided Hamming
code. Single bit errors are auto corrected.
unhamming_err (SCALAR)
Returns the original data from the provided Hamming
code, and a number counting the number of bytes that
were corrected. Single bit errors are auto corrected.
OTHER SUBROUTINES
Algorithm::Hamming::Perl::hamming_faster ()
This is an optional subroutine that will speed Hamming
encoding if it is run once at the start of the program.
It does this by using a larger (hash) cache of
preprocessed results. The disadvantage is that it uses
more memory, and can add several seconds to invocation
time. Only use this if you are encoding more than 1 Mb
of data.
use Algorithm::Hamming::Perl qw(hamming unhamming);
$data = "Hello";
$hamcode = hamming($data);
$original = unhamming($hamcode);
LIMITATIONS
This is Perl only and can be slow. The Hamming encoding used
can only repair a single bit error within a byte - ie if two
bits are damaged within the one byte then this encoding
cannot auto correct the error.
BUGS
Try not to join Hamming encoded strings together - this may
give results that look like a bug. If an odd number of input
byes is encoded, the output code is short half a byte - and
so is padded with '0' bits. Joining these with a string
concatenation will contain the padding bits that will
confuse decoding.
The above problem can occur when inputing and outputing
#!/usr/bin/perl
#
# example02 - example of converting bytes to hamming code, creating
# bit errors, then retrieving the original data.
#
# 18-Oct-2003 Brendan Gregg Created this.
use Algorithm::Hamming::Perl qw(hamming unhamming unhamming_err);
$data = "Hi";
### Hamming
$hamcode = hamming("$data");
print "input text: $data\n";
print "input text (as binary) : ",unpack("B*",$data),"\n";
print "hamming code (as binary) : ",unpack("B*",$hamcode),"\n";
$binary = unpack("B*",$hamcode);
$binary =~ s/1$/0/; # flip last bit (error on byte 2)
$binary =~ s/^010/011/; # flip third bit (error on byte 1)
$hamerr = pack("B*",$binary);
### UnHamming
($unham,$err) = unhamming_err($hamerr);
print "hamming code (with errors): $binary\n";
print "retrieved text (as binary): ",unpack("B*",$unham),"\n";
print "retrieved text : $unham\n";
print "bytes corrected: $err\n";
$data = "Hi";
$hamcode = hamming("$data");
$binary = unpack("B*",$hamcode);
ok($binary,"010011001000011001001101");
# 2. Test decoding
print "2. Hamming decoding test... ";
$unham = unhamming($hamcode);
ok($unham,"Hi");
# 3. Zero error value
print "3. Zero error value... ";
($unham,$err) = unhamming_err($hamcode);
ok($err,0);
# 4. Test error repair
print "4. Test error repair... ";
$errors = "011011001000011001001100";
$hamerr = pack("B*",$errors);
($unham,$err) = unhamming_err($hamerr);
ok($unham,"Hi");
# 5. Test non-zero error value
print "5. Test non-zero error value... ";
ok($err,2);
( run in 0.646 second using v1.01-cache-2.11-cpan-65fba6d93b7 )