Кодирование Хэмминга

[Last]

Здравствуйте, пытаюсь вот написать помехоустойчивое кодирование, столкнулся с проблемой. Есть некоторое число k, необоходимо проверить все числа от 2^0 до 2^k, причём проверять двоичное представление числа на предмет наличия единиц. Например: k = 3
Двоичное представление всех чисел от 1 до 8:
001 100 111
010 101
011 110

001, 011, 101, 111 - все числа, у которых в первом разряде 1
010, 011, 110, 111 - все числа, у которых во втором разряде 1
100, 101, 110, 111 - все числа, у которых в третьем разряде 1

Ума не приложу как это сделать средствами языка Си.

[Fedor666]

Имеется оператор "&&" (логическое И).

[Last]

Почитал Вики о проверке бита, понял о чём Вы, но как реализовать не совсем понял.
Мне нужно что-то вроде цикла:

for (i = 2; i < pow(2,k); i++)
{
    for (j = 1; j <= k; j++)
    {
        if (i & /*Здесь должно быть двоичное число с одним битом - единицей*/) {}
        /*Сдвигаем в числе бит влево */
    }
}

Интуиция подсказывает мне, что можно сделать это как-то проще, но я не знаю как. Да и такой цикл я не смогу записать, потому что не знаю как представить число в двоичной записи.
---------------------------
Апдейт: написал

i=1;
i<<1;
i<<1;
i<<1;

По-моему, программа должна была три раза сдвинуть бит влево, но ничего не произошло, единица осталась единицей.

[Fedor666]

Сообщение от Last

i<<1;

А где результат сохраняется?
Может попробовать так:

i=<<1;

[Last]

Выложу своё поделие, може кому понадобится =)

Пакет реализован в виде консольного приложения под Windows. Принцип работы – command-line utility, т.е. утилита, весь интерфейс которой заключён в параметрах, передаваемых при вызове.
Формат вызова:
hm <команда> <исходный файл> <файл-результат>
Команды:
h - помощь
e - закодировать сообщение
d - декодировать сообщение

//Алгоритм программы в книге "Дискретная математика для программистов", автор - Ф. Новиков
#include <math.h>
#include <stdio.h>
#include <float.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#define MAX_BUFFER 1024 

typedef struct list_t
{ 
	int d;
	struct list_t *next; 
}list;

int GetLength(char *s)
{
	int i = 0;
	while (s[i] != '\0')
		++i;
	return i;
}

void pl(list *p)
{	
	while (p->next != NULL)
	{
		printf("%i ", p->d);
		p = p->next;
	}
	printf("\n");

}

int Summ(list *p, int *b, int n, int flag)// если флаг - 1, то начинаем суммировать со второго элемента списка, иначе - с первого
{
	int x;
	
	if ((p->next != NULL) && (flag == 1)) 
		p = p->next;
	x = b[p->d - 1];
	if (p->next != NULL) p = p->next;
	while (p != NULL)
	{
		if (p->d - 1 <= n) 
			x ^=b[p->d - 1];
		p = p->next;
	}
	return x;
}

list *Add2List(list *p, int n)
{
	list *l = p;
	if (p == NULL)
	{
		p = (list*)malloc(sizeof(list));
		p->d = n;
		p->next = NULL;
	}
	else
	{
		while (l->next != NULL)
			l = l->next;
		l->next = (list*)malloc(sizeof(list));
		l = l->next;
		l->d = n;
		l->next = NULL;
	}
	return p;
}

list **GetList(int k, int n)
{
	list **v = (list**)calloc(k, sizeof(list*));
	int i, t, x;
	for (i = 0; i < k; i++)
	{
		v[i] = NULL;
	}

	for (i = 1; i <= n; i++)
	{
		x = 1;
		for (t = 0; t < k; t++)
		{
			
			if ((i & x) > 0) 
				v[t] = Add2List(v[t], i);
			x = x << 1;
		}
	}
	return v;
}

int *Geta(char *str, int length)
{
	
	int i, *a = (int*)calloc(length, sizeof(int));
	for (i = 0; i < length; i++)
	{
		if (str[i] == 48) 
			a[i] = 0;
		else
			a[i] = 1;
	}
	return a;

}

int CalcK(int n)
{
	int  i = 0, t = 0 ;
	while (t == 0)
	{
		if (pow(2,i) >= n + 1) t = 1;
		else ++i;
		if (n - i <= 0) return -1;
	}
	return i;

}
void FreeList(list *v)
{
	list *temp = v;
	while (temp != NULL)
	{
		v = v->next;
		free(temp);
		temp = v;
	}


}

void MyFree(list **v, int k)
{
	int i;
	for (i = 0; i < k; i++)
		FreeList(v[i]);
	free(v);
}

int Encode(char *arg1, char *arg2)
{
	int m, *a, *b, i, t, x, n, k;
	list **v;
	FILE *in, *out;
	char *str = (char*)malloc(MAX_BUFFER);
	in = fopen(arg1, "r");
	out = fopen(arg2, "w");
	fgets(str, MAX_BUFFER, in);	
	m = strlen(str);
	a = Geta(str, m);
	for (i = 0; i < m; i++)
		if ((a[i] != 0) && (a[i] != 1))
			return 1;					//1 - в исходном файле содержатся не только нули и единицы
	t = 0;
	i = 0;
	while (t == 0)
	{
		if (pow(2,i) >= m + i + 1) t = 1;
		else ++i;
	}
	k = i;
	n = m + k;
	b = (int*)malloc(n * sizeof(int));
	v = GetList(k, n);
	t = 0;
	x = 0;
	for (i = 0; i < n; i++)
	{
		if ((i + 1) == pow(2, t)) 
		{
			b[i] = -1;
			t++;
		}
		else
		{
			b[i] = a[x];
			x++;
		}
	}
	t = 0;
	for (i = 0; i < n; i++)
		if (b[i] == -1)
		{
			b[i] = Summ(v[t], b, n, 1);
			t++;
		}

	for (i = 0; i < n; i++)
		fprintf(out, "%i", b[i]);
	fclose(in);
	fclose(out);
	free(a); 
	free(b);
	free(str);
	MyFree(v, k);
	return 0;
}

int Decode(char *arg1, char *arg2)
{
	int m, *c, *b, i, t, n, k, *j, J;
	list **v;
	FILE *in, *out;
	char *str = (char*)malloc(MAX_BUFFER);
	in = fopen(arg1, "r");
	out = fopen(arg2, "w");
	fgets(str, MAX_BUFFER, in);
	n = strlen(str);
	c = Geta(str, n);
	k = CalcK(n);
	J = 0;
	if (k == -1) 
		return 1;
	m = n - k;
	j = (int*)malloc(k*sizeof(int));
	v = GetList(k, n);
	for (i = 0; i < k; i++)
	{
		j[i] = Summ(v[i], c, n, 0);
		if (j[i] != 0) 
			J = J + pow(2, i);
	}
	if (J != 0)
		c[J-1] = !c[J-1];
	t = 0;
	for (i = 0; i < n; i++)
	{
		if ((i+1) == pow(2, t)) 
			t++;
		else
			fprintf(out, "%i", c[i]);
	}
	fclose(in);
	fclose(out);
	free(c); 
	free(str);
	free(j);
	MyFree(v, k);
	return 0;
}

Мэйн не влез.

[Last]

main(int argc, char *argv[])
{
	int i = 0;
	char *command, *arg1, *arg2;
	if (argc < 3)
	{
		printf("You must input 3 parameters!\n");
		return 0;
	}
	command = (char*)malloc(strlen(argv[1]) + 1);
	arg1 = (char*)malloc(strlen(argv[2]) + 1);
	arg2 = (char*)malloc(strlen(argv[3]) + 1);
	strcpy(command, argv[1]);
	strcpy(arg1, argv[2]);
	strcpy(arg2, argv[3]);
	switch (command[0])
	{
	case 'h': 
		printf("\nUse syntax \"%%command%% %%input file%% %%output file%%\"\n"
			"Command list: \n"
			"h - help\n"
			"e - encode file\n"
			"d - decode file\n");
		break;
	case 'e':
		i = Encode(arg1, arg2);
		if (i == 1) printf("Error! Only 1 and 0 are allowed in source file!\n");
		else
			printf("Encoding has finished successfuly.\n");
		break;
	case 'd':
		i = Decode(arg1, arg2);
		if	(i == 1) 
			printf("Error! File must contain n+log(2,n) symbols!\n");
		else
			printf("Decoding has finished successfuly.\n");
		
		break;
	default: 
		printf("Wrong syntax, use h for help.\n");
		break;
	}
	free(command);
	free(arg1);
	free(arg2);
	return 0;
}

[Alkatraz31]

Всем привет....есть кто живой?...нужна помощь.