Cross-Interleaved Reed-Solomon Code¶

Cross-Interleaved Reed-Solomon Code (CIRC) — это метод помехоустойчивого кодирования, основанный на каскадном применении двух кодов Рида — Соломона с перемежением (интерливингом) данных. Разработан компанией Philips и Sony в начале 1980-х годов для использования в цифровых аудиодисках (Compact Disc, CD). CIRC обеспечивает высокую корректирующую способность при относительно низкой избыточности, что позволяет восстанавливать данные, повреждённые царапинами, пылью и производственными дефектами оптических носителей.

¶История создания

С появлением компакт-дисков в конце 1970-х годов возникла необходимость в надёжном кодировании, способном исправлять как случайные ошибки (например, шум считывания), так и пакетные ошибки (вызванные механическими повреждениями диска). Коды Рида — Соломона, предложенные Ирвингом Ридом и Гюставом Соломоном в 1960 году, обладали хорошими корректирующими свойствами, но для борьбы с длинными пакетами ошибок требовалось перемежение данных.

В 1980 году инженеры Philips и Sony, работавшие над стандартом «Красная книга» (Red Book) для CD, объединили два кода Рида — Соломона с разными параметрами и добавили перемежение. Полученная схема получила название Cross-Interleaved Reed-Solomon Code. Она была впервые применена в коммерческих CD-плеерах, выпущенных в 1982 году. Впоследствии CIRC лёг в основу многих других систем хранения данных, включая MiniDisc, DVD и некоторые форматы цифрового вещания.

¶Принцип работы

CIRC является каскадным (concatenated) кодом, где два кода Рида — Соломона работают последовательно: первый (C1) исправляет случайные ошибки, второй (C2) — пакетные. Между ними выполняется перемежение данных, которое «размазывает» пакетные ошибки по разным кодовым словам, делая их исправимыми.

¶Параметры кодов

• C1 (внутренний код): код Рида — Соломона (32, 28, 5) над полем GF(2^8). Длина кодового слова — 32 символа, из которых 28 — информационные, 4 — проверочные. Минимальное кодовое расстояние d_min = 5, что позволяет исправлять до 2 ошибок или обнаруживать до 4 ошибок в одном кодовом слове.
• C2 (внешний код): код Рида — Соломона (28, 24, 5) над полем GF(2^8). Длина — 28 символов, информационных — 24, проверочных — 4. Также имеет d_min = 5, исправляет до 2 ошибок.

¶Перемежение (интерливинг)

Перемежение в CIRC выполняется на двух уровнях:

1. Перемежение между C1 и C2: данные, закодированные C2, распределяются по нескольким кадрам C1 с задержкой (обычно 4 кадра). Это делается с помощью регистров сдвига.
2. Перемежение внутри C1: символы внутри кодового слова C1 дополнительно перемешиваются для защиты от коротких пакетных ошибок.

Конкретная схема перемежения в CIRC использует задержки от 1 до 4 кадров, что создаёт «перекрёстное» (cross) расположение данных — отсюда название.

¶Процесс кодирования и декодирования

Кодирование:

1. Исходные аудиоданные (24 байта на кадр) сначала кодируются внешним кодом C2, добавляя 4 проверочных байта.
2. Выполняется перемежение: полученные 28 байт распределяются по четырём последовательным кадрам с задержками.
3. Каждый кадр (28 байт) кодируется внутренним кодом C1, добавляя ещё 4 проверочных байта.
4. Итоговый кадр содержит 32 байта, которые записываются на диск.

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

1. Считывание кадра (32 байта) и декодирование C1: исправление до 2 ошибок. Если ошибок больше 2, кадр помечается как «стирание» (erasure).
2. Обратное перемежение: данные из разных кадров собираются в исходный порядок.
3. Декодирование C2: исправление ошибок с использованием информации о стираниях от C1. C2 может исправить до 2 ошибок или до 4 стираний.

¶Корректирующая способность

CIRC способен исправлять:

• До 3500 бит (около 2,5 мм дорожки) пакетных ошибок — это соответствует царапине длиной до 2,5 мм.
• До 12 000 бит (около 8,5 мм) ошибок с использованием интерполяции (восстановление данных по соседним отсчётам).

При этом избыточность CIRC составляет около 25% (4 проверочных байта на 24 информационных в каждом каскаде, но с учётом перемежения — примерно 33% от общего потока). Для сравнения, коды с аналогичной корректирующей способностью без перемежения потребовали бы значительно большей избыточности.

¶Применение

¶Компакт-диски (CD)

CIRC является обязательной частью стандарта «Красная книга» для всех аудио-CD. Он обеспечивает воспроизведение даже при наличии царапин, отпечатков пальцев и других дефектов. В сочетании с восьми-четырнадцати-модуляцией (EFM) CIRC образует физический уровень записи CD.

¶MiniDisc

В формате MiniDisc (1992) используется модификация CIRC под названием CIRC-7 (или CIRC-7/3), где параметры кодов изменены для работы с магнитооптическими носителями.

¶DVD

В DVD применяется более сложный вариант — RS-PC (Reed-Solomon Product Code), который является двухмерным каскадным кодом, основанным на тех же принципах, что и CIRC.

¶Другие системы

CIRC также используется в некоторых системах цифрового радиовещания (DAB), спутниковой связи и в ранних цифровых видеомагнитофонах.

¶Критика и ограничения

Несмотря на эффективность, CIRC имеет ряд недостатков:

• Задержка: перемежение вносит задержку в несколько миллисекунд, что критично для систем реального времени (например, видеоконференций).
• Сложность декодирования: требуется два этапа декодирования с обратным перемежением, что увеличивает вычислительные затраты.
• Ограниченная эффективность при очень длинных пакетах ошибок: при царапинах длиннее 8,5 мм CIRC может не справиться, и данные теряются.

Современные системы (например, Blu-ray) используют более совершенные коды, такие как LDPC (Low-Density Parity-Check), которые обеспечивают лучшую корректирующую способность при меньшей избыточности.

¶Интересные факты

• Название «Cross-Interleaved» отражает перекрёстное расположение данных между двумя кодами, а не просто последовательное перемежение.
• В процессе разработки CIRC инженеры Sony и Philips тестировали прототипы, процарапывая диски гвоздями и покрывая их пылью — код должен был гарантировать воспроизведение даже в таких условиях.
• CIRC не является единственным кодом в CD: дополнительно используется EFM (Eight-to-Fourteen Modulation) для синхронизации и снижения постоянной составляющей сигнала.

¶Источники

• Immink, K. A. S. (1998). Coding Techniques for Digital Recorders. Prentice Hall.
• Pohlmann, K. C. (2005). Principles of Digital Audio. McGraw-Hill.
• Стандарт «Красная книга» (IEC 60908).
• Документация Philips/Sony по CIRC (1980–1982).