17 / 16 / 1
Регистрация: 09.09.2013
Сообщений: 31
1

Поиск (расчет) кодовых последовательностей

09.09.2013, 18:07. Показов 2355. Ответов 11
Метки нет (Все метки)

Есть бинарные последовательности длиной 2^N. Для кодирования 2^N различных N-разрядных чисел смещением считывателей по этой шкале. Шкала круговая циклическая(те конец переходит в начало). Считыватели располагаются с определенным шагом.
Шкалы используются для кодирования угловых и линейный перемещений одной дорожкой.

Пример 3х разрядной шкалы с шагом 1:
00010111 кодирует числа: 000, 001, 010, 101, 011, 111, 110, 100 -все они различны.
Она же работает для шага 2. В этом случае числа будут такие: 000, 011, 001, 111, 010, 110, 100, 101 - они также различны.
Еще одно условие: вторая половина шкалы - есть инверсия первой.
Пример такой четырехразрядной с шагом 2:
0010000011011111.

Шестиразрядные последовательности нашел. Две семиразрядные тоже.
Необходимо оптимизировать алгоритм поиска повторов в N-разрядной шкале. Либо разработать метод расчета. Так же можно изменить алгоритм перебора.
Задача собственно в поиске 8++ разрядных последовательностей.
Сейчас буду отлаживать поиск на CUDA. Думал даже попробовать на Altera посчитать. Буду презнателен любым предложением.
Одна из моих наработок в матлабе:

Matlab M
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
function [C]= proschet
n=4; %Количество разрядов
k=2; %Шаг смещения 
n1=n-1;
A=strn(2,n);%Задание начального значения перебора в 10 - форме(для полных переборов =2 или 1) 
S=size(A);
s=S(1,2)/4;
s2=2*s;
A(s)=A(1);A(2*s)=1-A(1);A(3*s)=A(1);A(4*s)=1-A(1);%
C=A;
a=0;
c=1;
%Цикл перебора
while A(s)==A(1) %
    if povt(A,k,s2,n1)==0  
       C=[C;A];   
       %break; 
   end;
   A=steps(A,s);
end
clc;
s=size(C);
C=C(2:s(1,1),1:s(1,2)/4);
end
%Функция бинарного прибавления 1 к сопряженной последовательности
function A = steps(A,s)
for i=2:1:s
    if A(i)==1
        A(i)=0;
        A(i+s)=1;
        A(i+2*s)=0;
        A(i+3*s)=1;
    else
        A(i)=1;
        A(i+s)=0;
        A(i+2*s)=1;
        A(i+3*s)=0;
        break
    end
end
end
%Функция определеиния повторных кодов а=0 если шкала полнокодовая, a=1 если
%шкала содержит повторяющиеся коды
function a = povt(A,k,s,n1)
a=0;
for i=1:1:s
    B(i)=0;
    for j=0:1:n1
         B(i)=B(i)+2^j*A(i+k*j);      
    end 
    for j=1:1:i-1
        if B(j)==B(i) 
            a=1;
            break;
        end
    end
    if a==1;
        break
    end
end
end
%Функция генерации  по счету k, n-разрядной шкалы.
function A=strn(k,n)
a=de2bi(k);
s=size(a);
A=[a zeros(s(1,1),2^(n-1)-s(1,2))];
A=[A 1-A A 1-A];
end
Добавлено через 2 часа 41 минуту
еще вопрос допустим есть вектор 8 нулей -8единиц:
A=[zeros(8,1);ones(8,1)];
С помощь команд формируем матрицу кодов "B":
D=[A;A];
B=[A D(7:38) D(13:44) D(19:50) D(25:56)];
Как можно быстрыми функциями отследить есть ли повторяющиеся строки в матрице B
length(unique(bi2de(B))) - работает долго, циклить тоже не очень быстро получается
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.09.2013, 18:07
Ответы с готовыми решениями:

Найти количество возможных кодовых последовательностей(Порядок ввода цифр важен)
Известно, что код в кодовом замке может содержать от М до К цифр. Порядок ввода цифр важен....

Поиск кодовых слов в БД Azure
Доброго времени суток! Есть бесплатная бд на азуре и прототип приложения магазина windows 8.1 на...

Дартс 501 расчет и вывод последовательностей выигрыша
Всем привет, сегодня порадовали такой задачей: Напишите программу, которая рассчитывает и...

Поиск в текстовом файле последовательностей цифр по шаблону и последующий их поиск в именах файлов (с логом)
Уважаемые программисты и хорошие люди! К Вам обращается украинский юрист. Очень нужен bat-файл...

11
317 / 256 / 30
Регистрация: 30.03.2013
Сообщений: 755
21.09.2013, 11:15 2
http://www.mathworks.com/suppo... n=1-3W7N3H
1
17 / 16 / 1
Регистрация: 09.09.2013
Сообщений: 31
21.09.2013, 12:17  [ТС] 3
Немножко не то, если начать с простого:
Matlab M
1
A=de2bi([0:1:31]');
или
Matlab M
1
A=[0:1:31]';
Преобразование в строку делает этот массив бессмысленным так как 11,12 становится:"1112", так же и с двоичной формой
hist показывает не очень полезные вещи, да и работает не очень быстро.
Matlab M
1
2
3
4
5
[a,b]=hist(A)
a =
     4     3     3     3     3     3     3     3     3     4
b =
    1.5500    4.6500    7.7500   10.8500   13.9500   17.0500   20.1500   23.2500   26.3500   29.4500
и
Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
[a,b]=hist(A)
a =
    16    16    16    16    16
     0     0     0     0     0
     0     0     0     0     0
     0     0     0     0     0
     0     0     0     0     0
     0     0     0     0     0
     0     0     0     0     0
     0     0     0     0     0
     0     0     0     0     0
    16    16    16    16    16
b =
    0.0500    0.1500    0.2500    0.3500    0.4500    0.5500    0.6500    0.7500    0.8500    0.9500
На самом деле я уже отчаялся искать в матлаб, самое быстрое что получилось чтото типа:
Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
A=randi(2,32,1)-1;
A=[A;A];
B=A(1:32)+2*A(2:33)+4*A(3:34)+8*A(4:35)+16*(5:36);
a=0;
for i=0:31
 for j=i:32
  if B(i)== B(j)
   a=1;
  end
 end
 if a break; end;
end
Самое интересное, что рандом обрабатываеся тактов за 15. А прибавление единицы к двоичной строке где-то за тысячу. А преобразования типа bi2de и наоборот - около 10 тыс.
В общем скоро придет gtx 770, буду кудить.
Спасибо за ответ
0
317 / 256 / 30
Регистрация: 30.03.2013
Сообщений: 755
21.09.2013, 12:39 4
Приведите для примера кусок реальной 8-ми битной последовательности

Например повторы последовательности 00010111 можно искать путем расчета корреляции, представив саму последовательность в виде 8 целых чисел 0 0 0 1 0 1 1 1 , и где корреляция будет равна 1 там значит и находится нужная нам копия
0
17 / 16 / 1
Регистрация: 09.09.2013
Сообщений: 31
21.09.2013, 14:24  [ТС] 5
Цитата Сообщение от sergsh Посмотреть сообщение
Приведите для примера кусок реальной 8-ми битной последовательности

Например повторы последовательности 00010111 можно искать путем расчета корреляции, представив саму последовательность в виде 8 целых чисел 0 0 0 1 0 1 1 1 , и где корреляция будет равна 1 там значит и находится нужная нам копия
Суть в том что последовательность 00010111 кодирует 8 смещений:
000
001
101
011
111
110
100
И повторы нужно искать среди этих трехбитных комбинаций.
Это последовательности для дискретного кодирования угловых или линейных перемещений(шкалы круговые- те конец переходит в начало).
Сейчас я их проверяю так:
Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
A=[0 0 0 1 0 1 1 1]';
A=[A;A];
B=A(1:8)+2*A(2:9)+4*A(3:10);
a=0;
for i=1:7
  for j=i:8
    if B(i)==B(j)
      a=1;
      break;
    end;
  end;
  if a break; end;
end;
хотелось бы что-то побыстрее, потому что если перебирать 7-8-9 разрядные(считать 128-256-512 битные), получается очень долго.
0
317 / 256 / 30
Регистрация: 30.03.2013
Сообщений: 755
21.09.2013, 23:52 6
Цитата Сообщение от cujo Посмотреть сообщение
Суть в том что последовательность 00010111 кодирует 8 смещений:
000
001
101
011
111
110
100
И повторы нужно искать среди этих трехбитных комбинаций.
Все же непонятно, почему нельзя использовать сразу 00010111
Эта последовательность дает все время РАЗНЫЕ трехбитные комбинации ?
0
615 / 240 / 16
Регистрация: 31.07.2013
Сообщений: 376
22.09.2013, 05:10 7
Цитата Сообщение от cujo Посмотреть сообщение
Задача собственно в поиске 8++ разрядных последовательностей.
8-разрядные – это такие?

HTML5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
00000000100000011000001010000011 10000100100001011000011010000111
10001000100110001010100010111000 11001000110110001110100011111001
00101001001110010101100101101001 01111001100110101001101110011101
10011110100111111010101011101011 01101011111011011110111011111111
 
00000000100000011000001010000011 10000100100001011000011010000111
10001000100110001010100010111000 11001000110110001110100011111001
00101001001110010101100101101001 01111001100110101001101110011101
10011110100111111010101011101011 01101011111011101111011011111111
 
00000000100000011000001010000011 10000100100001011000011010000111
10001000100110001010100010111000 11001000110110001110100011111001
00101001001110010101100101101001 01111001100110101001101110011101
10011110100111111010101011101011 01101111011010111110111011111111
0
17 / 16 / 1
Регистрация: 09.09.2013
Сообщений: 31
22.09.2013, 11:06  [ТС] 8
Цитата Сообщение от Heidegger Посмотреть сообщение
8-разрядные – это такие?
Это так называемые рекурентные последовательности де Брейна, они считаются неприводимыми полиномами.
Единственный минус у них то что считыватели нужно располагать через 1 квант, с устранением неоднозначности в 1/2. Я бы хотел от этого избавиться вот и считаю.
Для 4-7 разрядов насчитал много, с 8 возникают проблемы. В принципе 10 -это идеальный вариант на данный момент. Больше не нужно из-за физических размеров кванта и нагрузок на промы.
Эта последовательность дает все время РАЗНЫЕ трехбитные комбинации ?
В том то и суть что этой последовательностью можно кодировать 3 разряда одной дорожкой, а я бы хотел кодировать 8(9-10)

Добавлено через 3 минуты
Цитата Сообщение от Heidegger Посмотреть сообщение
8-разрядные – это такие?
Меня интересуют 8 разрядные последовательности с шагом смещения 11-15 (в конкретно моем случае 14)
0
615 / 240 / 16
Регистрация: 31.07.2013
Сообщений: 376
22.09.2013, 14:25 9
Цитата Сообщение от cujo Посмотреть сообщение
Это так называемые рекурентные последовательности де Брейна, они считаются неприводимыми полиномами.
Приведенные выше три 28–разрядные последовательности таковыми являются (с шагом смещения 1)?

Цитата Сообщение от cujo Посмотреть сообщение
Для 4-7 разрядов насчитал много, с 8 возникают проблемы.
Количество циклов очень быстро растёт с увеличением n:
nчисло циклов
https://www.cyberforum.ru/cgi-bin/latex.cgi?\; \; \; \; 1https://www.cyberforum.ru/cgi-bin/latex.cgi?\; \; \; \; 1
21
32
416
52048
667108864
7144115188075855872

Так что после n = 6 перебрать их все нереально. Но я так понимаю, что они нужны не все, а только некоторое количество, причём с определённым шагом смещения (и шаг смещения 1 не интересует), так?
0
17 / 16 / 1
Регистрация: 09.09.2013
Сообщений: 31
22.09.2013, 16:58  [ТС] 10
именно так, шаг 1 не интересует.
Matlab M
1
2
3
4
5
6
A=[0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 1 1 0 1 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1];
A=[A A]';
B=A(1:256)+2*A(2:257)+4*A(3:258)+8*A(4:259)+16*A(5:260)+32*A(6:261)+64*A(7:262)+128*A(8:263);
length(unique(B))
ans =
   256
да, являются

в конечном счете нужна хотябы одна (и желательно с наименьшим числом групп нулей и единиц)

Шаги интересуют для семиразрядных от 5 до 10, для восьмиразрядных- от 10 до 17, для девяти-от 20 до 30
В итоге это нужно для равномерного размещения по считывателей по шкале.
0
615 / 240 / 16
Регистрация: 31.07.2013
Сообщений: 376
22.09.2013, 20:25 11
Цитата Сообщение от cujo Посмотреть сообщение
Шаги интересуют для семиразрядных от 5 до 10, для восьмиразрядных- от 10 до 17, для девяти-от 20 до 30
Можете показать пример высокоразрядной последовательности с большим шагом?

Добавлено через 1 минуту
Кликните здесь для просмотра всего текста
Насколько я понимаю, нужно что-то в этом роде:

HTML5
1
2
3
4
01100100110001001111100001010111
10000111000000101111001101101100
01101100011010110000001110011101
11101000101101010011010001110101
1
615 / 240 / 16
Регистрация: 31.07.2013
Сообщений: 376
26.09.2013, 17:28 12
Рекурсивный алгоритм, позволяющий построить все (при наличии достаточного количества ресурсов) одношаговые последовательности де Брёйна n-го порядка, заключается в следующем.

Цикл включает в себя все 2n чисел от 0 до 2n–1, поэтому не нарушая общности можно начинать построение последовательности с 0. Первые n–1 бит следующего числа совпадают с последними n+1 бит предыдущего, поэтому вторым членом последовательности может быть только 1. Разделим весь список чисел на голову H = [0, 1] и хвост T = [2, 2n–1].

Теперь последовательно будем искать кандидатов на продолжение списка H – их всегда не больше 2 (отличающихся в последнем бите). Если найдётся хотя бы один кандидат, добавляем его в голову, вычитаем из хвоста и продолжаем процедуру дальше, пока не закончатся кандидаты или хвост не окажется пуст – в последнем случае проверяем, является ли первый элемент головы циклически следующим за последним, и если это так, добавляем найденный список в множество циклов порядка n.

Алгоритм можно оптимизировать и дополнить для поиска также и последовательностей с произвольным шагом k . Для его реализации, возможно, лучше подойдут специально заточенные под рекурсию и работу со списками среды и языки типа Mathematica, Lisp, Haskell и т.п. Но и в матрично-ориентированном Matlab'е реализация тоже может оказаться достаточно удачной. Преимущество алгоритма заключается в том, что он целенаправленно строит последовательности с заданными свойствами, а не проверяет случайные последовательности на обладание ими.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.09.2013, 17:28

Поиск в тексте DOC-файлов последовательностей символов по шаблону и поиск найденных в TXT-файле (с логом)
Уважаемые программисты! Очень нужен bat-файл или скрипт, который решает такую задачу: ...

Поиск последовательностей единиц
Здравствуйте, прошу прощения заранее за возможно детский вопрос, но что-то не соображаю. Есть...

Поиск последовательностей в списке
Есть программка, которая генерирует числа с заданной вероятностью: import random m = 0 n = 0...

Поиск последовательностей состоящих из 0 и 1
Должно находить количество последовательностей из 5 элементов.И проверка впереди этими элементами...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.