Помехоустойчивое кодирование: реализуем алгоритм Хэмминга на java

В давние суровые времена, окутанные романтикой и легендами, программисты решали совсем другие задачи. Чего стоит, например, передача данных. Мы, скромные наследники гениев, работаем как правило не ниже уровня сокетов. А им приходилось измерять уровни сигнала, а ошибки измерений корректировать. Остались нам от них в наследство десяток алгоритмов коррекции ошибок разной сложности и мощности. Алгоритм Хэмминга достаточно "компромиссный" вариант. При относительной простоте он весьма эффективен: позволяет скорректировать ошибки в один бит на блок и обнаружить ошибки в два бита. Зачем нам может понадобиться его использовать? Например мы решили организовать передачу данных между двумя устройствами "нетрадиционным" способом. Сходу можно придумать три способа передачи данных между двумя Android-смартфонами: с помощью экрана и камеры, динамика и микрофона, вибрации и акселерометра. Как это применить - дело вашей фантазии, а вот как решить проблему коррекции ошибок при этом - подскажет моё маленькое приложение. Давайте рассмотрим реализацию алгоритма подробнее.

Кодируем

Алгорим Хэмминга - это вариант блочного кодирования. Это значит, что перед передачей данные разделяются на блоки, над которыми и выполняются операции. После получения обратное преобразование выполняется также с блоками, на которые разделяется полученный сигнал. Размер блока мы возьмём равным размеру символа такста. Для ASCII-символов это будет 7 бит, для кириллицы - 14. Из-за того, что приложение в моём примере будет автоматически определять длину слова по первому символу, мы не сможем с его помощью передать "смешанный" текст. Но для примера, думаю, это не важно.
Во-вторых, к данным добавляем контрольные биты. Биты помещаем в позиции 0, 1, 3, 7 блока. Значение контрольных бит зависит от остальных бит блока. Но не от всех, а только от тех, что удовлетворяют правилу: контрольный бит с номером N контролирует все последующие N бит через каждые N бит, начиная с позиции N. Что значит контролирует? Мы просто складываем значение всех "подконтрольных" бит, и если результат сложения - чётное число, то значение контрольного бита будет 0, иначе - 1.
Полный код класса, реализующего алгоритм будет ниже, пока посмотрим на реализацию кодирования, которое мы описали:

    private String encode(String in) {
        StringBuilder sb = new StringBuilder();
        char[] rezc = in.toCharArray();
        for (int i = 0; i < rezc.length / charLen; i++) {
            int[] c = slice(rezc, charLen, i);
            int[] cc = new int[encCharLen];
            for (int j = encCharLen - 1; j >= 0; j--) {
                if (j == 0 || j == 1 || j == 3 || j == 7) {
                    cc[j] = (sumElem(cc, j) % 2) == 0 ? 0 : 1;
                } else if (j == 2) {
                    cc[j] = c[j - 2];
                } else if (j > 3 && j < 7) {
                    cc[j] = c[j - 3];
                } else if (j > 7) {
                    cc[j] = c[j - 4];
                }
            }
            char[] d = new char[encCharLen];
            for (int j = 0; j < encCharLen; j++) {
                d[j] = Character.forDigit(cc[j], 2);
            }
            sb.append(d);
        }
        return sb.toString();
 
    }
 
    private int sumElem(int[] arr, int f) {
        int rez = 0;
        int count = 0;
        int delim = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i <= f) {
                continue;
            } else if (count < f) {
                rez += arr[i];
                count++;
            } else if (count == f) {
                rez += arr[i];
                count++;
                delim = 0;
            } else if (delim < f) {
                delim++;
            } else if (delim == f) {
                delim++;
                count = 0;
            }
        }
        return rez;
    }

Тут charLen - длина блока без контрольных бит. Её мы вычисляем ранее, при преобразовании входных данных в бинарную строку.

Декодируем

Как всегда с такими алгоритмами, реализация декодирования сложнее.

private String decode(String raw) {
        char[] rawc = raw.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < rawc.length / encCharLen; i++) {
            int[] c = slice(rawc, encCharLen, i);
            int[] p = new int[4];
            p[0] = c[0];
            p[1] = c[1];
            p[2] = c[3];
            p[3] = c[7];
            p[0] = ((sumElem(c, 0) % 2) == 0 && p[0] == 0) || ((sumElem(c, 0) % 2) != 0 && p[0] == 1) ? 0 : 1;
            p[1] = ((sumElem(c, 1) % 2) == 0 && p[1] == 0) || ((sumElem(c, 1) % 2) != 0 && p[1] == 1) ? 0 : 1;
            p[2] = ((sumElem(c, 3) % 2) == 0 && p[2] == 0) || ((sumElem(c, 3) % 2) != 0 && p[2] == 1) ? 0 : 1;
            p[3] = ((sumElem(c, 7) % 2) == 0 && p[3] == 0) || ((sumElem(c, 7) % 2) != 0 && p[3] == 1) ? 0 : 1;
            int d = p[0] * 1 + p[1] * 2 + p[2] * 4 + p[3] * 8;
            if (d >= encCharLen) {
                d = d / 2;
            }
            if (d != 0) { // correction
                c[d] = c[d] == 0 ? 1 : 0;
            }
            char[] r = new char[charLen];
            for (int l = 0, q = 0; l < charLen; q++) {
                if (q == 0 || q == 1 || q == 3 || q == 7) {
                    continue;
                }
                r[l] = Character.forDigit(c[q], 2);
                l++;
            }
            sb.append(r);
        }
        return sb.toString();
    }

Тут мы делаем следующее:

1. Режем исходную бинарную строку на блоки (строка 5)
2. Получаем значения контрольных бит (с. 7-10)
3. Рассчитываем значения исходя из полученных данных и сверяем их значениями контрольных бит (с. 11-14). Тут мы получаем так называемый "симптом", то есть массив отклонений контрольных бит. Если данный контрольный бит не совпадает с рассчитанным, то значение симптома для этого бита будет 1, иначе - 0.
4. Находим в какой позиции блока произошла ошибка и корректируем ошибку, просто инвертируя бит. (стр. 15-21). 
5. Выбрасываем контрольные биты, возвращая блок к первоначальному виду и преобразуем его к виду бинарно строки. (стр. 22-29)

Полный код класса со всеми вспомогательными методами:

public class HammingCoder {
 
    private int charLen;
    private int encCharLen;
    private boolean isHamming;
 
    public HammingCoder() {
    }
 
    public void setHammingEnabled(boolean isHamming) {
        this.isHamming = isHamming;
    }
 
    public String encodeBytes(byte[] raw) {
        String rez = byteToBinary(raw);
        if (isHamming) {
            rez = encode(rez);
        }
        return rez;
    }
 
    public String encodeString(String in) {
        if (in.length()>0) {
            String rez = stringToBinary(in);
            if (isHamming) {
                rez = encode(rez);
            }
            return rez;
        } else return "";
    }
 
    private String encode(String in) {
        StringBuilder sb = new StringBuilder();
        char[] rezc = in.toCharArray();
        for (int i = 0; i < rezc.length / charLen; i++) {
            int[] c = slice(rezc, charLen, i);
            int[] cc = new int[encCharLen];
            for (int j = encCharLen - 1; j >= 0; j--) {
                if (j == 0 || j == 1 || j == 3 || j == 7) {
                    cc[j] = (sumElem(cc, j) % 2) == 0 ? 0 : 1;
                } else if (j == 2) {
                    cc[j] = c[j - 2];
                } else if (j > 3 && j < 7) {
                    cc[j] = c[j - 3];
                } else if (j > 7) {
                    cc[j] = c[j - 4];
                }
            }
            char[] d = new char[encCharLen];
            for (int j = 0; j < encCharLen; j++) {
                d[j] = Character.forDigit(cc[j], 2);
            }
            sb.append(d);
        }
        return sb.toString();
 
    }
 
    public String decodeString(String raw) {
        if (raw.length()>0) {
            if (isHamming) {
                return stringFromBinary(decode(raw));
            } else {
                return stringFromBinary(raw);
            }
        } else return "";
    }
 
    public byte[] decodeBytes(String raw) {
        if (raw.length()>0) {
            if (isHamming) {
                return byteFromBinary(decode(raw));
            } else {
                return byteFromBinary(raw);
            }
        } else return new byte[0];
    }
 
    private String decode(String raw) {
        char[] rawc = raw.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < rawc.length / encCharLen; i++) {
            int[] c = slice(rawc, encCharLen, i);
            int[] p = new int[4];
            p[0] = c[0];
            p[1] = c[1];
            p[2] = c[3];
            p[3] = c[7];
            p[0] = ((sumElem(c, 0) % 2) == 0 && p[0] == 0) || ((sumElem(c, 0) % 2) != 0 && p[0] == 1) ? 0 : 1;
            p[1] = ((sumElem(c, 1) % 2) == 0 && p[1] == 0) || ((sumElem(c, 1) % 2) != 0 && p[1] == 1) ? 0 : 1;
            p[2] = ((sumElem(c, 3) % 2) == 0 && p[2] == 0) || ((sumElem(c, 3) % 2) != 0 && p[2] == 1) ? 0 : 1;
            p[3] = ((sumElem(c, 7) % 2) == 0 && p[3] == 0) || ((sumElem(c, 7) % 2) != 0 && p[3] == 1) ? 0 : 1;
            int d = p[0] * 1 + p[1] * 2 + p[2] * 4 + p[3] * 8;
            if (d >= encCharLen) {
                d = d / 2;
            }
            if (d != 0) { // correction
                c[d] = c[d] == 0 ? 1 : 0;
            }
            char[] r = new char[charLen];
            for (int l = 0, q = 0; l < charLen; q++) {
                if (q == 0 || q == 1 || q == 3 || q == 7) {
                    continue;
                }
                r[l] = Character.forDigit(c[q], 2);
                l++;
            }
            sb.append(r);
        }
        return sb.toString();
    }
 
    private int sumElem(int[] arr, int f) {
        int rez = 0;
        int count = 0;
        int delim = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i <= f) {
                continue;
            } else if (count < f) {
                rez += arr[i];
                count++;
            } else if (count == f) {
                rez += arr[i];
                count++;
                delim = 0;
            } else if (delim < f) {
                delim++;
            } else if (delim == f) {
                delim++;
                count = 0;
            }
        }
        return rez;
    }
 
    private int[] slice(char[] in, int size, int part) {
        int[] rez = new int[size];
        for (int i = 0; i < size; i++) {
            char curr = in[part * size + i];
            rez[i] = Character.digit(curr, 2);
        }
        return rez;
    }
 
    private String byteToBinary(byte[] raw) {
        StringBuilder sb = new StringBuilder();
        for (byte b : raw) {
 
            StringBuilder sbb = new StringBuilder("00000000");
            for (int bit = 0; bit < 8; bit++) {
                if (((b >> bit) & 1) > 0) {
                    sbb.setCharAt(7 - bit, '1');
                }
            }
            sb.append(sbb);
            charLen = 8;
            encCharLen = charLen + 4;
        }
        return sb.toString();
    }
 
    private String stringToBinary(String in) {
        StringBuilder sb = new StringBuilder();
        for (char c : in.toCharArray()) {
            String binstr = Integer.toBinaryString(c);
            sb.append(binstr);
            charLen = binstr.length();
            encCharLen = charLen + 4;
        }
        return sb.toString();
    }
 
    private byte[] byteFromBinary(String in) {
        byte[] rez = new byte[in.length() / charLen];
        int i = 0;
        while (in.length() >= charLen) {
            String slice = in.substring(0, charLen);
            in = in.substring(charLen);
            rez[i] = Byte.parseByte(slice, 2);
            i++;
        }
        return rez;
    }
 
    private String stringFromBinary(String in) {
        StringBuilder sb = new StringBuilder();
        while (in.length() >= charLen) {
            String slice = in.substring(0, charLen);
            in = in.substring(charLen);
            int charCode = Integer.parseInt(slice, 2);
            sb.append(new Character((char) charCode).toString());
        }
        return sb.toString();
    }
}

Класс работает как с строками (методы encodeString и decodeString) так и с массивами байт (методы encodeBytes и decodeBytes).