Рубрики

Генерация n-битных кодов серого

Учитывая число n, сгенерируйте битовые комбинации от 0 до 2 ^ n-1 так, чтобы последовательные шаблоны отличались на один бит.

Примеры:

Following is 2-bit sequence (n = 2)
  00 01 11 10
Following is 3-bit sequence (n = 3)
  000 001 011 010 110 111 101 100
And Following is 4-bit sequence (n = 4)
  0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 
  1110 1010 1011 1001 1000

Вышеуказанные последовательности являются кодами серого различной ширины. Ниже приводится интересная схема в кодах серого.

n-битные коды Грея могут быть сгенерированы из списка (n-1) -битных кодов Грея, используя следующие шаги.
1) Пусть список (n-1) -битных кодов Грея равен L1. Создайте другой список L2, который противоположен L1.
2) Измените список L1, добавив префикс «0» во всех кодах L1.
3) Измените список L2, добавив префикс «1» во всех кодах L2.
4) Объединить L1 и L2. Связанный список является обязательным списком n-битных кодов Грея.

Например, ниже приведены шаги для создания 3-битного списка кодов Грея из списка 2-битных списков кодов Грея.
L1 = {00, 01, 11, 10} (список 2-битных кодов серого)
L2 = {10, 11, 01, 00} (обратный L1)
Префикс всех записей L1 с '0', L1 становится {000, 001, 011, 010}
Префикс всех записей L2 с '1', L2 становится {110, 111, 101, 100}
Объединяя L1 и L2, мы получаем {000, 001, 011, 010, 110, 111, 101, 100}

Чтобы сгенерировать n-битные коды Грея, мы начнем со списка 1-битных кодов Грея. Список 1-битного кода Грея: {0, 1}. Мы повторяем вышеописанные шаги для генерации 2-битных кодов Грея из 1-битных кодов Грея, затем 3-битных кодов Грея из 2-битных кодов Грея до тех пор, пока число битов не станет равным n. Ниже приводится реализация этого подхода.

C ++

// C ++ программа для генерации n-битных кодов Грея
#include <iostream>
#include <string>
#include <vector>

using namespace std;

  
// Эта функция генерирует все n-битные коды Грея и печатает
// сгенерированные коды

void generateGrayarr(int n)

{

    // базовый вариант

    if (n <= 0)

        return;

  

    // 'arr' будет хранить все сгенерированные коды

    vector<string> arr;

  

    // начинаем с однобитного шаблона

    arr.push_back("0");

    arr.push_back("1");

  

    // Каждая итерация этого цикла генерирует 2 * i кода из ранее

    // сгенерированные я коды.

    int i, j;

    for (i = 2; i < (1<<n); i = i<<1)

    {

        // Введите ранее сгенерированные коды снова в arr [] в обратном порядке

        // заказ. Ни arr [] не имеет двойного числа кодов.

        for (j = i-1 ; j >= 0 ; j--)

            arr.push_back(arr[j]);

  

        // добавляем 0 к первой половине

        for (j = 0 ; j < i ; j++)

            arr[j] = "0" + arr[j];

  

        // добавляем 1 ко второй половине

        for (j = i ; j < 2*i ; j++)

            arr[j] = "1" + arr[j];

    }

  

    // выводим содержимое arr []

    for (i = 0 ; i < arr.size() ; i++ )

        cout << arr[i] << endl;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    generateGrayarr(3);

    return 0;

}

Джава

// Java-программа для генерации n-битных кодов Грея

import java.util.*;

class GfG { 

  
// Эта функция генерирует все n-битные коды Грея и печатает
// сгенерированные коды

static void generateGrayarr(int n) 

    // базовый вариант

    if (n <= 0

        return

  

    // 'arr' будет хранить все сгенерированные коды

    ArrayList<String> arr = new ArrayList<String> (); 

  

    // начинаем с однобитного шаблона

    arr.add("0"); 

    arr.add("1"); 

  

    // Каждая итерация этого цикла генерирует 2 * i кода из ранее

    // сгенерированные я коды.

    int i, j; 

    for (i = 2; i < (1<<n); i = i<<1

    

        // Введите ранее сгенерированные коды снова в arr [] в обратном порядке

        // заказ. Ни arr [] не имеет двойного числа кодов.

        for (j = i-1 ; j >= 0 ; j--) 

            arr.add(arr.get(j)); 

  

        // добавляем 0 к первой половине

        for (j = 0 ; j < i ; j++) 

            arr.set(j, "0" + arr.get(j)); 

  

        // добавляем 1 ко второй половине

        for (j = i ; j < 2*i ; j++) 

            arr.set(j, "1" + arr.get(j)); 

    

  

    // выводим содержимое arr []

    for (i = 0 ; i < arr.size() ; i++ ) 

        System.out.println(arr.get(i)); 

  
// Программа драйвера для проверки вышеуказанной функции

public static void main(String[] args) 

    generateGrayarr(3); 

}

python3

# Python3 программа для генерации n-битных кодов Грея

import math as mt

  
# Эта функция генерирует все n бит Грея
# кодирует и печатает сгенерированные коды

def generateGrayarr(n):

  

    # базовый вариант

    if (n <= 0):

        return

  

    # 'arr' будет хранить все сгенерированные коды

    arr = list()

  

    # начать с однобитного шаблона

    arr.append("0")

    arr.append("1")

  

    # Каждая итерация этого цикла генерирует

    # 2 * я коды из ранее сгенерированных я кодов.

    i = 2

    j = 0

    while(True):

  

        if i >= 1 << n:

            break

      

        # Введите явно сгенерированные коды

        # снова в arr [] в обратном порядке.

        # Ни arr [] не имеет двойного числа кодов.

        for j in range(i - 1, -1, -1):

            arr.append(arr[j])

  

        # добавить 0 к первой половине

        for j in range(i):

            arr[j] = "0" + arr[j]

  

        # добавить 1 ко второй половине

        for j in range(i, 2 * i):

            arr[j] = "1" + arr[j]

        i = i << 1

  

    # prcontents of arr []

    for i in range(len(arr)):

        print(arr[i])

  
Код водителя

generateGrayarr(3)

  
# Этот код добавлен
# Мохит Кумар 29

C #

using System;

using System.Collections.Generic;

  
// C # программа для генерации n-битных кодов Грея

public class GfG

{

  
// Эта функция генерирует все n-битные коды Грея и печатает
// сгенерированные коды

public static void generateGrayarr(int n)

{

    // базовый вариант

    if (n <= 0)

    {

        return;

    }

  

    // 'arr' будет хранить все сгенерированные коды

    List<string> arr = new List<string> ();

  

    // начинаем с однобитного шаблона

    arr.Add("0");

    arr.Add("1");

  

    // Каждая итерация этого цикла генерирует 2 * i кода из ранее

    // сгенерированные я коды.

    int i, j;

    for (i = 2; i < (1 << n); i = i << 1)

    {

        // Введите ранее сгенерированные коды снова в arr [] в обратном порядке

        // заказ. Ни arr [] не имеет двойного числа кодов.

        for (j = i - 1 ; j >= 0 ; j--)

        {

            arr.Add(arr[j]);

        }

  

        // добавляем 0 к первой половине

        for (j = 0 ; j < i ; j++)

        {

            arr[j] = "0" + arr[j];

        }

  

        // добавляем 1 ко второй половине

        for (j = i ; j < 2 * i ; j++)

        {

            arr[j] = "1" + arr[j];

        }

    }

  

    // выводим содержимое arr []

    for (i = 0 ; i < arr.Count ; i++)

    {

        Console.WriteLine(arr[i]);

    }

}

  
// Программа драйвера для проверки вышеуказанной функции

public static void Main(string[] args)

{

    generateGrayarr(3);

}
}

  

  // Этот код предоставлен Shrikant13


Выход:

000
001
011
010
110
111
101
100

Эта статья составлена Рави Чандрой Энаганти . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Генерация n-битных кодов серого

0.00 (0%) 0 votes