Как повысить скорость алгоритма построения допинг-матрицы

Question

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

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

2. Остальные строки должны содержать определенное числоединичные записи, sb_degree.Как я объясню вкратце, в этом и заключается проблема.

3. Чтобы матрица подходила для требуемых целей (допирование квантового кода LDPC), в каждой строке и столбце должен быть хотя бы одинединица входа.По сути, матрица не может иметь всю нулевую строку или столбец.

Мой код работает достаточно хорошо для определенных комбинаций параметров входного алгоритма: p (количество строк сединичная запись), m1 (количество строк в M), N (количество столбцов в M) и sb_degree (количество единиц в строках, имеющих более одной записи в единицу).Например, у него нет проблем с поиском матриц при условии, что значения p и sb_degree не слишком велики или малы соответственно.Однако из-за характера проблемы, которую решают эти матрицы, мне требуются матрицы с большим значением p (около 65% от значения m1) и небольшим значением sb_degree.Это становится проблемой для моего алгоритма, так как небольшие значения sb_degree делают поиск матрицы, которая удовлетворяет вторым и третьим требованиям конструкции, трудной задачей.

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

Алгоритм называется M = Create_Doping_Matrix(m1,N,p,sb_degree) и реализован следующим образом

M = zeros(m1,N);
p_indexes = randperm(m1,p);
all_indexes = 1:m1;
idx = ~ismember(all_indexes,p_indexes);
loc = find(idx~=0);
c_indexes = randperm(N,p);
% Create the rows with a single unit entry
for ii=1:p
    M(p_indexes(ii),c_indexes(ii)) = 1;
end
M_orig = M;
% Create the rows with more than a single unit entry
for jj = 1:length(loc)
    M(loc(jj), randperm(N,sb_degree))=1;
end

while nnz(sum(M,1)) ~= N % Check that there are no all-zero rows
    M = M_orig;
    for jj = 1:length(loc)
        M(loc(jj), randperm(N,sb_degree))=1;
    end
end

Answer 1

Вместо случайного размещения значений, пока все столбцы не имеют записи, я бы назначил строку для всех столбцов, а затем заполнил бы строки m1-p, пока у каждого из них не будет sb_degree ненулевых записей .

M = zeros(m1,N);
p_indexes = randperm(m1,p);
all_indexes = 1:m1;
idx = ~ismember(all_indexes,p_indexes);
loc = find(idx~=0);
c_indexes = randperm(N,p);
% Create the rows with a single unit entry
for ii=1:p
    M(p_indexes(ii),c_indexes(ii)) = 1;
end

Код здесь тот же. Теперь убедитесь, что в каждом столбце есть ровно одна ненулевая запись. Обратите внимание, что этим процессом loc строкам может быть назначено более одного значения 1, вплоть до sb_degree.

% Add one entry to each unfilled column of M on an unfilled row of M(loc,:)
missing = find(sum(M,1) == 0);

for fillcol = missing
   addtoidx = randi(numel(loc));   % select random row from loc 
   fillrow = loc(addtoidx);   % row number in M
   M(fillrow, fillcol) = 1;
   if (sum(M(fillrow,:)) >= sb_degree)   % this row is now full 
      loc(addtoidx) = [];   % remove it from loc 
   end
end

И, наконец, заполните loc строки sb_degree.

% Fill the rows that need more than a single unit entry
% but still contain less than sb_degree
for jj = 1:length(loc)   
   thisrow = M(loc(jj),:);   % unfilled row from M
   emptycols = find(thisrow == 0);   % indices of columns of thisrow not yet filled
   fillidx = randperm(numel(emptycols), sb_degree - sum(thisrow));
   M(loc(jj), emptycols(fillidx))=1;
end