Как рассчитать код Хэмминга без преобразования в двоичную строку? - PullRequest
Новая
       74

Как рассчитать код Хэмминга без преобразования в двоичную строку?

0 голосов
/ 16 мая 2019

Я пытаюсь решить проблему, которая сводится к нахождению кода Хемминга без использования двоичной строки с длинным числом в Java.

Я не понимаю, как мы можем это сделать, я искал вво многих местах, таких как объяснение в Википедии и , это я нашел в Интернете , но всем им нужна двоичная строка для работы, но здесь в этом случае я не могу их использовать.

У меня естьдлинное число, представляющее входной двоичный файл, теперь мне нужно найти код Хемминга.

Насколько я понимаю, у меня могут быть пустые места в позициях 1, 2, 8 ... в этом двоичном файле.Теперь я могу поставить 0 или 1 в этом месте, используя логическое значение, которое говорит мне, является ли это четным или нечетным.

Я написал код, используя строку и списки, но мне нужно это без использования строк или списков. 

String text = new Scanner(System.in).next() ;
    int len = text.length() ;
    ArrayList codearray = new ArrayList() ;
    ArrayList pos_arr = new ArrayList() ;


    while (!(len + r + 1 <= Math.pow(2, r))) {
        r++;
    }


    System.out.println("Number of parity bits : "+r);

    for (int i=0 ; i<len + r  ; i++) {

        if (IsPowerTwo(i+1) ){
            codearray.add("?") ;
        }else {
            codearray.add(text.charAt(j));
            j++ ;
        }
    }


    System.out.println(codearray.toString());

    //to determine the position of parity bits
    for (int i=0 ; i< codearray.size() ; i++) {
        if (codearray.get(i) == "?") {
            int k ,s=1;
            // For Debugging.
            //System.out.println("Calculate at position " + (i+1) ) ;
            for (k = i ; k < codearray.size() ; k++){

                if (i==0) {
                    k++ ;
                    pos_arr.add(k);
                }else {

                    pos_arr.add(k+1);
                    if(s % (i+1) == 0) {
                        k += i+1 ;
                    }
                }
                s++ ;

            }

            checkOnes(pos_arr,codearray,i) ;
            pos_arr.clear();
        }


    }

    System.out.println("Code word: ");
    Arr_to_Str(codearray) ;
}

public static boolean IsPowerTwo(int num){
    int checked = num & num -1 ;
    if (checked == 0 ){
        return true ;
    }else {
        return false ;
    }

}
public static void checkOnes(ArrayList array, ArrayList codearray, int position ){

    int count =0;

    for (int i=0 ; i < array.size(); i++) {
        int index = (int) array.get(i) -1 ;
        if (codearray.get(index) == "?"  ) {
            codearray.set(index,0) ;
        }

        int num = Integer.parseInt(codearray.get(index).toString()) ;
        if (num == 1  ) {
            count++ ;
        }
        if(count % 2 ==0 ){
            codearray.set(position, 0) ;
        }else {
            codearray.set(position, 1) ;
        }

    }
}

public static void Arr_to_Str(ArrayList array){
    for (int i=0;i<array.size();i++){
        System.out.print(array.get(i));
    }
}

Но для этого требуется, чтобы я работал с двоичной строкой или списком, как мне это сделать?сделайте то же самое с длинными числами, такими как, скажем, 210.

Я действительно новичок в битовых манипуляциях и, следовательно, не могу обернуться вокруг этого.Буду очень признателен за любую помощь.

1 Ответ

2 голосов
/ 17 мая 2019

Кодирование Хэмминга может быть реализовано с помощью битовых манипуляций.Вероятно, это даже проще, чем со строкой.Вот несколько идей по реализации.

Схема алгоритма кодирования Хэмминга следующая: 

input_val is a long int to encode
output_val_is the long int result
for s in 0..5
  count number of bits in input_val whose position has bit s set
  add to output_val the parity of this count
  add next 2^s bits from input_val to output_val

Действительно, есть две проблемы: получение четности определенного набора битов и создание выходных данных.с битовыми сдвигами.

Подсчет установленных битов по заданному шаблону *

Для кодирования Хэмминга необходимо вычислить четность на подмножестве битов (шаблон).Шаблоны: 010101010101 ... 01 для первого шага, 001100110 ... 00110 для второго шага и т. Д. И могут быть закодированы в массив mask, индексированный по номеру шага.mask [0] = 0x5555555555555555, mask [1] = 0x6666666666666666, mask [2] = 0xf0f0f0f0f0f0f0f0, mask [3] = 0xff00ff00ff00ff00 и т. д.

Чтобы получить эту четность, проще считать и подсчитать числочтобы получить младший балл этого подсчета.В Java есть функция, которая дает число битов в целом числе.Следовательно, единственной требуемой здесь операцией является 

count=Integer.bitcount(input_val & masks[s]) ;

, где s - номер этапа вычисления.

Затем необходимо добавить к выводу count & 0x1, чтобы добавить четность счета.

Добавление бита к целому числу

Оно тесно связано с количеством битов в вашем входном и выходном размере значения.Для простоты я предполагаю, что обе ваши данные могут быть закодированы на 64 битах.Это означает, что у вас есть 6 битов четности, и что ваши входные данные являются только частью вашей переменной, и что 6 MSB input_data равны нулю.

Чтобы добавить младший бит целого числа v к output_valпроще добавить его в позиции результата MSB и сдвинуть его вправо.После добавления 64 битов все на своем месте.Обратите внимание, что output_val должен быть без знака, чтобы избежать арифметического смещения вправо.

Итак, чтобы добавить младший бит v к output_val, нужно выполнить операцию 

output_val = (output_val >> 1) | (v<< 63);

v << 63 извлечьLSB и поставить его в положение MSB.ИЛИ добавляет к смещенному результату. </p>

Чтобы добавить несколько битов (например, k), можно использовать 

output_val = (output_val >> k) | (v<< (64-k));

Так что окончательная реализация (для улучшения) будет выглядеть примерно так: 

input_queue = input_val;
output_val = 0;
for (s=0; s<6;s++) {'
  count=Integer.bitcount(input_val & masks[s]) ; // compute parity
  output_val = (output_val >> 1) | (count << 63);// add parity to output
  output_val = (output_val >> (1<<s)) | (input_queue << (64-(1<<s)); 
                                   // add 2^s LSB of input to output
  input_queue >>=(1<<s);           // suppress 2^s bits form input_queue
}
...