-
Notifications
You must be signed in to change notification settings - Fork 364
/
hammingCode.java
87 lines (73 loc) · 3.21 KB
/
hammingCode.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.util.ArrayList;
import java.util.List;
public class hammingCode {
public static int calculateParityBits(int m, int low, int high) {
// Binary algorithm to find the required number of bits
if (high == 0) {
high = m + 1;
}
int r = (low + high) / 2;
if (low == high) {
return low;
} else if (Math.pow(2, r) >= r + m + 1) { // r = redundant bit, m = data bit
return calculateParityBits(m, low, r);
} else {
return calculateParityBits(m, r + 1, high);
}
}
public static boolean isPowerOfTwo(int num) {
// Performs a bitwise AND operation between num and num - 1.
// This operation turns off the rightmost set bit in num (i.e., the least significant bit).
// If the result of the bitwise AND operation is zero, it means that num had only one set bit (power of 2)
// before the bitwise operation, and that bit was turned off. In this case, the number is considered a power of 2.
return (num & (num - 1)) == 0;
}
public static int calculateParityValue(List<Character> encodedBlock, int pos) {
// Count the number of ones corresponding to the parity bit
int count = 0;
for (int i = 0; i < encodedBlock.size(); i++) {
int bit = encodedBlock.get(i);
if (bit == '1' && (((i + 1) & pos) != 0)) {
count++;
}
}
return count % 2;
}
public static String hammingEncode(String message) {
int m = message.length(); // Length of the message
int r = calculateParityBits(m, 0, 0); // Calculate the number of parity bits
int blockLength = m + r; // Total length of the encoded block
// Create a list to store the encoded bits
List<Character> encodedBlock = new ArrayList<>();
int dataBit = 0;
// Iterate over the block and copy the data
for (int position = 1; position <= blockLength; position++) {
if (isPowerOfTwo(position)) {
encodedBlock.add('P'); // Mark as parity bit
} else {
encodedBlock.add(message.charAt(dataBit)); // Data bit, copy from the message
dataBit++;
}
}
// Iterate over the parity bits in the encoded block
for (int position = 1; position <= blockLength; position++) {
if (encodedBlock.get(position - 1) == 'P') {
// Calculate and assign the required parity value
int parity = calculateParityValue(encodedBlock, position);
encodedBlock.set(position - 1, (parity % 2 == 0) ? '0' : '1');
}
}
// Convert the list of characters to a string
StringBuilder encodedMessage = new StringBuilder();
for (char bit : encodedBlock) {
encodedMessage.append(bit);
}
return encodedMessage.toString();
}
public static void main(String[] args) {
String message = "11110010010"; // Example message
String encodedMessage = hammingEncode(message);
System.out.println("Message entered: " + message);
System.out.println("Encoded Message: " + encodedMessage);
}
}