news.shamcode.ru | Как работают коды Spotify

В первой части мы разобрали общие технические принципы функционирования кодов платформы Spotify, и в завершении я написал, что неуверенность в некоторых деталях не позволила мне реализовать собственный конвертер штрихкодов в URI. Однако благодаря дополнительному исследованию и активной помощи от участников StackOverflow теперь я это преобразование выполнить могу.

Если вы первую статью не читали, то стоит начать с нее. Я опубликовал ее, в том числе, на Reddit, где она породила интересную дискуссию. Случилось так, что сам Людвиг Стригеус, ключевой разработчик Spotify, который и придумал эти коды, заглянул на огонек и поделился дополнительной информацией по их созданию и стоящей за ними логикой.

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

Кодирование URI в штрихкод Spotify

На мой взгляд, проще всего понять штрихкоды, начав с URI и проследовав по всему процессу кодирования.

Медиа-ссылка

Сначала Spotify генерирует медиа-ссылку для URI. Эта ссылка кодируется в штрихкод и связывает его с URI. Spotify поддерживает базу данных сопоставлений медиа-ссылок с URI.
Медиа-ссылки позволяют ресурсу отслеживать сканирование кодов, в теории дают возможность пересопоставлять их и просто выглядят в кодированном виде красивее. Если бы Spotify кодировал весь URI, то выглядел бы он примерно как показано ниже, и сканировать его в таком виде было бы уже сложнее.

Начнем с медиа-ссылки 57639171874, указывающей на следующий плейлист: spotify:user:spotify:playlist:37i9dQZF1DWZq91oLsHZvy (Indie x Running).

Эту медиа-ссылку можно выразить в виде 37-битного двоичного числа:

57639171874 -> 0100010011101111111100011101011010110

Вычисление CRC

Далее для медиа-ссылки вычисляются биты циклической проверки избыточности. Делается это для оценки целостности данных. (Еще одним инструментом проверки контрольных сумм, используемым нами повседневно для проверки номеров кредитных карт, является алгоритм Луна).

Spotify использует CRC-8, которому соответствует следующий полином:

x^8 + x^2 + x + 1

В полной записи он выглядит так:

1x^8 + 0x^7 + 0x^6 + 0x^5 + 0x^4 + 0x^3 + 1x^2 + x + 1
[1, 0, 0, 0, 0, 0, 1, 1, 1]

Вычисление CRC происходит по следующим этапам:

1. Заполнение тремя битами справа.

01000100 11101111 11110001 11010110 10110000

2. Реверсирование байт.

00100010 11110111 10001111 01101011 00001101

3. Стандартное вычисление CRC (старший бит слева).

11001100

4. Реверсирование CRC.

00110011

5. Инвертирование бит.

11001100

6. Присоединение к результату из шага 1.

01000100 11101111 11110001 11010110 10110110 01100
|----------Media Ref--------------------||--CRC--|

Вот простая версия калькулятора crc (шаг 3):

def crc(data, polynomial):
    # выполнить операцию xor для данных с полиномом в каждом вхождении 1.
    # Остаток вернуть в виде контрольной суммы.
    n = len(polynomial) - 1
    initial_length = len(data)
    check_bits = data + [0] * n
    for i in range(initial_length):
        if check_bits[i] == 1:
            for j, p in enumerate(polynomial):
                check_bits[i + j] = check_bits[i + j] ^ p
    return check_bits[-n:]

С помощью проверки бит можно удостовериться в том, что полученные данные соответствуют переданным «отправителем»:

def check_crc(data, polynomial, check_bits):
    full_data = data + check_bits
    for i in range(len(data)):
        if full_data[i] == 1:
            for j, p in enumerate(polynomial):
                full_data[i + j] = full_data[i + j] ^ p
    return 1 not in full_data
data = [0,0,1,0,0,0,1,0,1,1,1,1,0,1,1,1,1,0,0,0,1,1,1,1,0,1,1,0,1,0,1,1,0,0,0,0,1,1,0,1]
check = [1,1,0,0,1,1,0,0]
poly = [1,0,0,0,0,0,1,1,1]
print(check_crc(data, poly, check))
# True

Сверточное кодирование

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

Патент Spotify не очень ясен относительно того, какое сверточное кодирование выполняется:

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

Однако участник StackOverflow под ником «Doyle» определил, что Spotify использует следующие генераторные полиномы:

g0 = 1011011
g1 = 1111001

Этот полином представляет, какие биты входных данных должны быть проXORены вместе в скользящем окне.

Откусывание хвоста (tail_bite)
Прежде, чем мы начнем вычислять биты четности, нужно добавить в начало потока последние 6 бит данных:

01000100 11101111 11110001 11010110 10110110 01100
                                           |-----|

001100 01000100 11101111 11110001 11010110 10110110 01100
|----|

В виде альтернативы можно дополнить выходные данные нулями, но разработчики Spotify решили пойти по пути «откусывания хвоста».

Кодирование
Одновременно можно фокусироваться только на одном генераторе. Ниже представлен пошаговый проход по процессу генерации бит четности для g0. Полином я развернул наоборот, потому что в этом примере его проще отобразить справа налево.

Bit #0
001100010001001110111111110001110101101011011001100
1101101 <- generator polynomial (mask)
-------
0001000 = 1 (xor the bits together)

Bit #1
001100010001001110111111110001110101101011011001100
 1101101 <- generator polynomial (mask)
 -------
 0100001 = 0 (xor the bits together)

Bit #2
001100010001001110111111110001110101101011011001100
  1101101 <- generator polynomial (mask)
  -------
  1100000 = 0 (xor the bits together)

Bit #3
001100010001001110111111110001110101101011011001100
   1101101 <- generator polynomial (mask)
   -------
   1000100 = 0 (xor the bits together)

Bit #4
001100010001001110111111110001110101101011011001100
    1101101 <- generator polynomial (mask)
    -------
    0001000 = 1 (xor the bits together)
Продолжаем до конца потока входных бит:
Bit #45
001100010001001110111111110001110101101011011001100
                                            1101101 <- generator polynomial (mask)
                                            -------
                                            1001100 = 1 (xor the bits together)

Результат кодирования с помощью первого генератора, g0:

100011100111110100110011110100000010001001011

Результат кодирования с помощью g1:

110011100010110110110100101101011100110011011

Ниже приведен (простой) алгоритм для вычисления бит четности:

def encode(bits: List[int], polynomial: List[int], tail_bite=False):
    """Сверточное кодирование потока бит с помощью генераторного полинома.
    Если tail_bite == True, добавляем хвост входных данных. В противном случае заполняем нулями.   """
    if tail_bite:
        tail = bits[-(len(polynomial) - 1):]
    else: 
        tail = [0 for i in range(len(polynomial) - 1)]
    full = tail + bits
    polynomial.reverse() # Реверсируем полином, так как работаем в обратном направлении
    parity_bits = []
    for i in range(len(bits)):
        parity = 0
        for j in range(len(polynomial)):
            parity ^= full[i + j] * polynomial[j]
        parity_bits.append(parity)
    return parity_bits

Затем эти две последовательности битов четности чередуются (abab…):

1 0 0 0 1 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 0 1 1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1
 1 1 0 0 1 1 1 0 0 0 1 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 1 1 0 0 1 1 0 0 1 1 0 1 1
result:
110100001111110000101110111100110100111100011010111001110001000101011000010110000111001111

Перфорирование
На этом этапе мы перешли от 45 к 90 бит. Скорость этого сверточного кода равна ½ (на один входной бит генерируется 2 бита четности).

Скорость ½ в данном контексте маловата (рекомендую почитать статью о скорости работы QR-кодов). Ее можно повысить путем «перфорирования» кода, подразумевающего удаление каждого третьего бита. Так мы увеличим скорость до ¾:

110100001111110000101110111100110100111100011010111001110001000101011000010110000111001111
11 10 00 11 11 00 10 11 11 10 11 10 11 10 01 01 11 00 11 00 00 10 01 00 01 11 00 11 00 11
result:
111000111100101111101110111001011100110000100100011100110011

Это равнозначно перфорированию последовательностей двух бит четности с паттернами 101 и 110 перед их чередованием. Перфорирование – это красивый и простой способ увеличить скорость кода после оценки частоты ожидаемых ошибок.

Пермутация

После этого Spotify перемешивает данные, чтобы в случае утраты всего штриха ошибки распределились по всей структуре:

Процесс перемешивания используется для распределения потенциальных ошибок (например, если утрачивается целый штрих/интервал). В итоге утраченные биты в кодовом слове идут непоследовательно, что увеличивает эффективность упреждающей коррекции ошибок, когда утрачивается целый штрих или интервал. Далее, чтобы отсканировать оптический код после того, как длины найденных штрихов достоверно конвертированы в биты, эти биты перемешиваются обратно в правильном порядке.
Источник

Перемешивание бит происходит путем выбора из входных данных каждого 7-го (по модулю 60).

def permute(bits, step=7):
    for i in range(len(bits)):
        yield bits[(i * step) % len(bits)]

Вход и результат:

111000111100101111101110111001011100110000100100011100110011
111100110001110101101000011110010110101100111111101000111000

Сопоставление с высотами штрихов
В завершении с помощью кода Грея биты сопоставляются с высотами штрихов, чьи значения варьируются от от 0 до 7:

Десятичный	                 Двоичный	              Грей
0	                         000	                 000
1	                         001	                 001
2	                         010	                 011
3	                         011	                 010
4	                         100	                 110
5	                         101	                 111
6	                         110	                 101
7	                         111	                 100

111 100 110 001 110 101 101 000 011 110 010 110 101 100 111 111 101 000 111 000
 5   7   4   1   4   6   6   0   2   4   3   4   6   7   5   5   6   0   7   0

В качестве точек привязки добавляются три дополнительных штриха: в начале, в конце и в 12-й позиции:

[0]5741466024[7]3467556070[0]

В результате получается итоговый код Spotify:

Декодирование

Еще раз повторим, зачем мы прошли через процесс вычисления CRC и сверточного кодирования данных:

Сверточные коды позволяют нам исправлять ошибки в сообщении путем отправки вместе с этим сообщением «избыточных» бит.
CRC позволяет клиенту проверять достоверность декодированного кода Spotify. Если контрольные биты оказываются не верны, клиент может просканировать код повторно. Если же они сходятся, тогда клиент может обратиться к серверам Spotify. Как говорит Людвиг: «Я решил включить CRC, чтобы позволить клиенту с легкостью отклонять неверные коды без необходимости обращения к бэкенду».

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

Сверточное декодирование

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

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

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

Рабочее решение

Если вы хотите увидеть рабочий декодер, то можете ознакомиться с этим кодом. Вам понадобится получить от Spotify личный токен доступа, потому что код должен обращаться к их серверу поиска соответствий media_ref -> uri. Отмечу, что в коде задействуется решение Дойла из разряда линейной алгебры.

Я проверил это решение еще на нескольких кодах Spotify:

heights: [0, 6, 6, 0, 7, 6, 0, 2, 2, 3, 1, 7, 0, 7, 6, 4, 6, 1, 4, 7, 4, 1, 0]
media ref: 26560102031
uri: spotify:track:1ykrctzPhcSS9GS3aHdtMt

heights: [0, 2, 6, 7, 1, 7, 0, 0, 0, 0, 4, 7, 1, 7, 3, 4, 2, 7, 5, 6, 5, 6, 0]
uri: spotify:user:jimmylavallin:playlist:2hXLRTDrNa4rG1XyM0ngT1
media ref: 67775490487

heights: [0, 5, 7, 4, 1, 4, 6, 6, 0, 2, 4, 7, 3, 4, 6, 7, 5, 5, 6, 0, 5, 0, 0]
uri: spotify:user:spotify:playlist:37i9dQZF1DWZq91oLsHZvy
media ref: 57639171874

Думаю, будет уместно поделиться показавшимся мне забавным предложением из статьи об алгоритме Витерби:

Вскоре после этого, в работе, вышедшей 23 мая 1968 года, Джим Омура заметил, что VA (алгоритм Витерби) был просто стандартным решением прямого динамического программирования для декодирования по максимальному правдоподобию динамической системы с дискретным временем и конечным состоянием, наблюдаемой в шуме без запоминания.

Не знаю как вы, но я бы не стал описывать «стандартное решение прямого динамического программирования для декодирования по максимальному правдоподобию динамической системы с дискретным временем и конечным состоянием, наблюдаемой в шуме без запоминания» словом «простое».

Целью моей статьи было попытаться объяснить процесс кодирования Spotify доступным образом. Надеюсь, что мне это удалось.

Дополнительные материалы

Как спрятать мусор в базе Spotify и превратить это в квест

CRC Rocksoft

Reed-Solomon Codes and the Exploration of the Solar System

High-Rate Punctured Convolutional Codes for Soft Decision Viterbi Decoding

Viterbi Decoding of Convolutional Codes

Convolutional codes (MIT lecture notes)

Viterbi Decoder

Punctured Convolutional Encoding

Performance of concatenated codes for deep space missions

Convolutional Codes and State Machine View/Trellis (MIT Slides)

The Error Correcting Codes Page

Explanation on Math Stack Exchange

Как работают коды Spotify — часть 2