Итеративное декодирование LDPC/турбо, полярные коды — разбираем на C++ и сравниваем с MATLAB

Когда моделируешь помехоустойчивые коды, декодер обычно остаётся чёрным ящиком: пишешь ldpcDecode(llr, cfg, 30), comm.TurboDecoder или dvbs2ldpc(1/2) — и получаешь красивый «водопад» BER, не заглядывая внутрь. А самое интересное в современных кодах именно там: не в том, как закодировать, а в том, как декодер из зашумлённого сигнала достаёт правильные биты.
Первая часть заканчивалась предложением: «если интересно разобрать итеративное декодирование LDPC/турбо в деталях или полярные коды с последовательным отменением — пишите в комментариях». Написали — так что эта статья и есть ответ на запрос из комментариев. Читать первую часть необязательно: там мы прошли эволюцию кодов в сотовой связи от GSM до 5G по BER‑кривым в MATLAB, а всё нужное я напомню по ходу. Здесь — вскрываем сами декодеры.

https://habr.com/ru/articles/1043922/

Алгоритмы и Структуры данных

OSDEV: Разработка аллокатора на С++ часть 3. Финальный аллокатор со списками свободных блоков

Оглавление
Часть 1
Часть 2
Часть 4
Весь код можно найти в этом репозитории
В третьей статье пойдет речь уже о готовом аллокаторе который вполне пригоден для распределения памяти. Он полностью переписан, но идея та же самая, неявный список свободных блоков с граничными тегами сверху и снизу, но с массивом списков свободных блоков. Т.е. по сути с бинами.

https://habr.com/ru/articles/1045692/

Алгоритмы и Структуры данных

Консольный рендерер Мандельброта с методом возмущений с 1e-308

Я сделал это! Это огромный повод для гордости. Теперь программа работает по тем же математическим принципам, что и самые передовым фрактальным в мире! Но в самый первый я скажу вот:

Благодарности
Этот проект использует передовые математические алгоритмы и идеи динамического управления фазой орбит, разработанные фрактальным сообществом. Особая благодарность авторам и исследователям с Fractal Forums, чей совместный труд лег в основу этого движка:

https://habr.com/ru/articles/1045660/

Алгоритмы и Структуры данных

Обучение универсальным навыкам в IT

Дисклеймер: статья отражает личное мнение автора и не претендует на абсолютную истину. Если у вас есть дополнения, замечания или альтернативный взгляд — буду рад обсудить это в комментариях.

По данным Stack Overflow Developer Survey 2024, более 65% разработчиков регулярно изучают новые технологии. Однако есть навыки, которые остаются актуальными независимо от языка программирования, стека или конкретной компании. Именно такие навыки я и хотел собрать в этой статье.

Речь пойдёт о базовом понимании и обучению Linux, Git, SQL и NoSQL, алгоритмов и структур данных, а также английского языка. Это те вещи, которые, на мой взгляд, дают хороший фундамент практически для любого направления в IT.

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

https://habr.com/ru/articles/1045808/

Алгоритмы и Структуры данных

Интервью с самим собой

Надеюсь, что данная публикация не будет воспринята, как пиар. Просто мне хотелось поделиться некоторыми соображениями на тему технологического решения ориентированного на специалистов прикладников. Не секрет, что не так-то просто найти общий язык между специалистами различных специальностей, в том числе между специалистами предметниками и ИТ-специалистами реализующими прикладные задачи. Идеи, затронутые в интервью, могут быть использованы для реализации ваших собственных приложений совершенно свободно. Единственная просьба не забыть упомянуть об источнике информации.

https://habr.com/ru/articles/1043834/

Алгоритмы и Структуры данных

В умелых руках и sed — балалайка или пишем «Морской бой» на регулярках

Морской бой — простая игра, в которую можно научить играть даже первоклассника. Тридцать лет назад реализацию этой игры на компьютере можно было продавать. Десять лет назад написание морского боя на любимом языке было хорошим упражнением для будущего программиста. Сегодня, когда с написанием такой игры справится и продвинутая нейронка, сложно кого-то удивить очередной ее реализацией. Но я все же попробую.
Я решил написать морской бой на sed — потоковом текстовом редакторе из набора стандартных юниксовых утилит. Обычно его применяют для того, чтобы заменить в потоке или файле одну регулярку на другую. Но дополнительные директивы, которые есть в sed, формируют Тьюринг-полный язык, на котором теоретически можно написать что угодно.

https://habr.com/ru/articles/1042940/

Алгоритмы и Структуры данных

В умелых руках и sed — балалайка или пишем «Морской бой» на регулярках

Морской бой — простая игра, в которую можно научить играть даже первоклассника. Тридцать лет назад реализацию этой игры на компьютере можно было продавать. Десять лет назад написание морского боя на любимом языке было хорошим упражнением для будущего программиста. Сегодня, когда с написанием такой игры справится и продвинутая нейронка, сложно кого-то удивить очередной ее реализацией. Но я все же попробую.
Я решил написать морской бой на sed — потоковом текстовом редакторе из набора стандартных юниксовых утилит. Обычно его применяют для того, чтобы заменить в потоке или файле одну регулярку на другую. Но дополнительные директивы, которые есть в sed, формируют Тьюринг-полный язык, на котором теоретически можно написать что угодно.

https://habr.com/ru/articles/1042940/

Алгоритмы и Структуры данных

Самый старый кирпич трансформера наконец переизобрели. DeepSeek взял матрицу из 1967 года

За attention-механизм с 2017 года брались сотни раз: sparse attention, linear attention, MoE, MLA, скользящие окна, что только не. А вот residual connection, остаточная связь, та самая x + F(x) из ResNet 2016 года, простояла почти десять лет нетронутой. Её просто унаследовали из résnet'ов, воткнули в трансформер и забыли.
31 декабря 2025-го DeepSeek выложил на arXiv препринт, где взялся именно за этот кирпич. И что показательно, загрузил его на arXiv лично основатель компании Liang Wenfeng, он же в соавторах. Когда основатель сам публикует статью, это обычно значит, что она ляжет в следующую флагманскую модель. Так и вышло: mHC поехал в DeepSeek V4, который выкатили 24 апреля 2026-го.
Разберём, что они сделали, почему это работает и при чём тут матрица из шестидесятых.

https://habr.com/ru/articles/1044096/

Алгоритмы и Структуры данных

Я попробовал считать нейросетевой слой в конечном поле Галуа GF(137): 4x по памяти, ARM NEON и честные ограничения

В современных нейросетях критически важно, сколько физической памяти занимает каждый параметр. В этой работе я попытался уйти от классического float32 в нейросетевом слое к uint8 без квантования. Для этого все вычисления проводились сразу по правилам арифметики остатков в конечном поле Галуа GF(137).
Стоит сказать, что это не замена обычному инференсу и не попытка доказать, что все должны срочно переписать модели на вычеты по модулю 137. Я взял небольшой слой, байтовые веса, нативное ядро, ARM NEON и несколько базовых реализаций для сравнения.
Спойлер: на маленьком контрольном запуске байтовая модель заняла около 1.63 KB вместо 6.50 KB, при этом 1000 прямых проходов в ARM NEON режиме заняли всего 12.1 ms. В лучшем случае на выборке это дает около 4x по памяти и до 4.86x по времени относительно базовой NumPy float32-реализации.

https://habr.com/ru/articles/1044172/

Алгоритмы и Структуры данных

Архиватор рождённый из теории предельного сжатия вселенной

В 1996 году, во время учёбы в военном институте по специальности «программирование», на занятиях по кодированию данных мне пришла идея. Что если построить бинарное преобразование по правилу:

https://habr.com/ru/articles/1046081/

Алгоритмы и Структуры данных

Публичный мок АА в Яндексе: опыт, который не заменит никакая подготовка

Современный разработчик не упускает возможностей — отказаться от мок-собеса в Яндекс я не смог. Отдельная благодарность двум людям, без которых этого опыта не было бы: Оле Рыбаковой, которая предложила попробовать себя в прохождении мока — и это дорогого стоит, когда человек помогает, не будучи обязан это делать. И Наде Безносовой, продюсеру мероприятия — она ввела нас в формат и сделала всё для нашего комфорта.

https://habr.com/ru/articles/1059542/

Алгоритмы и Структуры данных

Я попробовал считать нейросетевой слой в конечном поле Галуа GF(137): 4x по памяти, ARM NEON и честные ограничения

В современных нейросетях критически важно, сколько физической памяти занимает каждый параметр. В этой работе я попытался уйти от классического float32 в нейросетевом слое к uint8 без квантования. Для этого все вычисления проводились сразу по правилам арифметики остатков в конечном поле Галуа GF(137).
Стоит сказать, что это не замена обычному инференсу и не попытка доказать, что все должны срочно переписать модели на вычеты по модулю 137. Я взял небольшой слой, байтовые веса, нативное ядро, ARM NEON и несколько базовых реализаций для сравнения.
Спойлер: на маленьком контрольном запуске байтовая модель заняла около 1.63 KB вместо 6.50 KB, при этом 1000 прямых проходов в ARM NEON режиме заняли всего 12.1 ms. В лучшем случае на выборке это дает около 4x по памяти и до 4.86x по времени относительно базовой NumPy float32-реализации.

https://habr.com/ru/articles/1044172/

Алгоритмы и Структуры данных

Как я создавал алгоритм шифрования под влиянием шифра Вернама

Самодельные шифры — зло. Зачем создавать собственный шифр, если есть… Кстати, а что есть? Есть известные шифры, которые пока ещё никто не взломал и есть не менее известные шифры, которые сначала считались надёжными, но потом в них нашли серьёзные уязвимости. А ещё у каждого (пока ещё) стойкого шифра есть как свои сторонники, так и свои противники. Хуже того, регулярно находятся чудаки, которые не разбираются в шифровании, но создают свои собственные шифры. И ладно бы молча пользовались ими сами, так они ещё их публикуют. А данная статья — лишь очередное подтверждение этого явления.

https://habr.com/ru/articles/1044174/

Алгоритмы и Структуры данных

Большинство исследований в компьютерной томографии нельзя воспроизвести

Мы не собирались писать эту статью. Мы всего лишь хотели воспроизвести результаты открытого бенчмарка ICASSP-2024 по низкодозовой компьютерной томографии, сравнить их с алгоритмами Smart Tomo Engine и понять свое место относительно опубликованных baseline и SOTA-решений.
Сначала всё шло по плану. Потом более быстрый алгоритм неожиданно оказался точнее более медленного. Затем на картах ошибок начали повторяться странные структуры. А спустя несколько дней выяснилось, что часть измеряемого качества может определяться не реконструкцией томографических данных, а особенностями самого бенчмарка.
Так обычная задача воспроизведения результатов превратилась в расследование. В этой статье мы покажем, что именно удалось обнаружить, почему воспроизводимость в компьютерной томографии оказывается намного сложнее, чем кажется, и почему хороший результат в таблице лидеров не всегда означает хороший алгоритм.

https://habr.com/ru/companies/smartengines/articles/1044162/

Алгоритмы и Структуры данных

Большинство исследований в компьютерной томографии нельзя воспроизвести

Мы не собирались писать эту статью. Мы всего лишь хотели воспроизвести результаты открытого бенчмарка ICASSP-2024 по низкодозовой компьютерной томографии, сравнить их с алгоритмами Smart Tomo Engine и понять свое место относительно опубликованных baseline и SOTA-решений.
Сначала всё шло по плану. Потом более быстрый алгоритм неожиданно оказался точнее более медленного. Затем на картах ошибок начали повторяться странные структуры. А спустя несколько дней выяснилось, что часть измеряемого качества может определяться не реконструкцией томографических данных, а особенностями самого бенчмарка.
Так обычная задача воспроизведения результатов превратилась в расследование. В этой статье мы покажем, что именно удалось обнаружить, почему воспроизводимость в компьютерной томографии оказывается намного сложнее, чем кажется, и почему хороший результат в таблице лидеров не всегда означает хороший алгоритм.

https://habr.com/ru/companies/smartengines/articles/1044162/

Алгоритмы и Структуры данных

О подборе игроков

Нет, Арпад Эло не придумал матчмейкинг. Он придумал рейтинговую систему. Да и вообще, его больше шахматы занимали, хотя везде и пишут, что он физик. Вот, кстати, его формула расчета мат. ожидания исхода партии:

https://habr.com/ru/articles/1044120/

Алгоритмы и Структуры данных

Преобразование числа в строку методом умножения на 10

В этом тексте рассматривается метод преобразование двоичного числа в строку без использования операций деления и остатка.

Обычно для преобразования целого числа в строку используется метод последовательного деления данного числа на основание требуемой системы исчисления и сбор остатков, которые соответствуют цифрам в десятичной системе.

https://habr.com/ru/articles/1044764/

Алгоритмы и Структуры данных

Преобразование Фурье в цифровой обработке сигналов. Часть 1: Дискретное преобразование Фурье

Преобразование Фурье - это математический инструмент, который переводит сигнал из временной области в частотную. Проще говоря, оно раскладывает сложный сигнал на простые составляющие - синусоиды и косинусы разных частот, амплитуд и фаз. Как химик разлагает вещество на отдельные элементы, так и преобразование Фурье «разбирает» сигнал на его частотные компоненты.
В этой статье мы начинаем погружение в одну из фундаментальных тем цифровой обработки сигналов (ЦОС) - дискретное преобразование Фурье (ДПФ). Именно ДПФ служит математической основой для понимания более сложных методов спектрального анализа и является отправной точкой для изучения всех остальных видов преобразования Фурье в ЦОС.

https://habr.com/ru/articles/1045118/

Алгоритмы и Структуры данных

Как мы перепридумали голосовую активацию для Яндекс Дропс и уместили новую модель в 200 килобайт

Голосовая активация в умных колонках — задача в целом решённая: несколько микрофонов, стабильное питание от розетки, хороший процессор. А вот перенести то же самое в наушники оказалось совсем другой историей.

Крошечный аккумулятор, мало памяти, чип с жёсткими ограничениями по тактовой частоте, да ещё и с кое‑какими неожиданным сюрпризами на уровне SDK. Всё это потребовало переосмыслить с нуля архитектуру споттера (компонента, который распознаёт обращение «Алиса» прямо на устройстве).

Меня зовут Григорий Афанасенко, я работаю в команде голосовых технологий Яндекса. Сегодня мы запустили Яндекс Дропс — первое носимое ИИ‑устройство с Алисой AI. В этой статье я расскажу, как мы адаптировали споттер под железо наушников, какие решения пришлось принять, где мы наступили на грабли и что планируем делать дальше.

https://habr.com/ru/companies/yandex/articles/1042706/

Алгоритмы и Структуры данных

Как я реализовал передачу диалога из ИИ-консультанта сайта в MAX

Всё началось с простого вопроса: почему малый бизнес теряет клиентов ночью?

Клиент заходит на сайт в 23:00, пишет в чат — и уходит. Потому что менеджер спит. Утром менеджер видит сообщение, перезванивает — а клиент уже купил у конкурента.

Стандартное решение — чат-бот. Но обычный чат-бот либо ограничен заранее заданными сценариями, либо требует интеграции с крупными облачными LLM. (отвечает по скриптам), либо слишком дорогой (GPT-4 за десятки тысяч в месяц), либо хранит данные за рубежом, что не всегда удобно для российского бизнеса.

Я решил сделать иначе.

https://habr.com/ru/articles/1045412/

Алгоритмы и Структуры данных