Код с малой плотностью проверок на чётность

Код с малой плотностью проверок на чётность (LDPC-код от англ. Low-density parity-check code, LDPC-code, низкоплотностный код) — используемый в передаче информации код, частный случай блочного линейного кода с проверкой чётности. Особенностью является малая плотность значимых элементов проверочной матрицы, за счёт чего достигается относительная простота реализации средств кодирования.

Также называют кодом Галлагера, по имени автора первой работы на тему LDPC-кодов.

Предпосылки

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

При передаче информации её поток разбивается на блоки определённой (чаще всего) длины, которые преобразуются кодером (кодируются) в блоки, называемыми ключевыми словами. Ключевые слова передаются по каналу, возможно с искажениями. На принимающей стороне декодер преобразует ключевые слова в поток информации, исправляя (по возможности) ошибки передачи.

Теорема Шеннона утверждает, что при определённых условиях вероятность ошибки декодирования (то есть невозможность декодером исправить ошибку передачи) можно уменьшить, выбрав большую длину ключевого слова. Однако, данная теорема (и работа вообще) не показывает, как можно выбрать большую длину, а точнее как эффективно организовать процесс кодирования и декодирования информации с большой длиной ключевых слов. Если предположить, что в кодере и декодере есть некие таблицы соответствия между входным блоком информации и соответствующим кодовым словом, то такие таблицы будут занимать очень много места. Для двоичного симметричного канала без памяти (если говорить упрощённо, то на вход кодера поступает поток из нулей и единиц) количество различных блоков составляет 2ⁿ, где n — количество бит (нулей или единиц) которые будут преобразовываться в одно кодовое слово. Для 8 бит это 256 блоков информации, каждый из которых будет содержать в себе соответствующее кодовое слово. Причём кодовое слово обычно большей длины, так как содержит в себе дополнительные биты для защиты от ошибок передачи данных. Поэтому одним из способов кодирования является использование проверочной матрицы, которые позволяют за одно математическое действие (умножение строки на матрицу) выполнить декодирование кодового слова. Аналогичным образом каждой проверочной матрице соответствует порождающая матрица, аналогичным способом одной операцией умножения строки на матрицу генерирующей кодовой слово.

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

Первой работой на эту тему стала работа Роберта Галлагера «Low-Density Parity-Check Codes» 1963 года (основы которой были заложены в его докторской диссертации 1960 года). В работе учёный описал требования к таким кодам, описал возможные способы построения и способы их оценки. Поэтому часто LDPC-коды называют кодами Галлагера. В русской научной литературе коды также называют низкоплотностными кодами или кодами с малой плотностью проверок на чётность.

Однако, из-за сложности в реализации кодеров и декодеров эти коды не использовались. Лишь много позже, с развитием телекоммуникационных технологий, снова возрос интерес к передаче информации с минимальными ошибками. Несмотря на сложность реализации по сравнению с турбо-кодом, отсутствие преград к использованию (незащищённость патентами) сделало LDPC-коды привлекательными для телекоммуникационной отрасли, и фактически стали стандартом де-факто. В 2003 году LDPC-код, вместо турбо-кода, стал частью стандарта DVB-S2 спутниковой передачи данных для цифрового телевидения. Аналогичная замена произошла и в стандарте DVB-T2 для цифрового наземного телевизионного вещания.

LDPC-коды

LDPC-коды описываются низкоплотностной проверочной матрицей, содержащей в основном нули и относительно малое количество единиц. По определению, если каждая строка матрицы содержит ровно <math>k < n</math> и каждый столбец ровно <math>j < r</math> единиц, то код называют регулярным (в противном случае — нерегулярным). В общем случае количество единиц в матрице имеет порядок <math>O\left( n \right)</math>, то есть растёт линейно с увеличением длины кодового блока (количества столбцов проверочной матрицы).

Обычно рассматриваются матрицы больших размеров. Например, в работе Галлагера в разделе экспериментальных результатов используются «малые» количества строк n=124, 252, 504 и 1008 строк (число столбцов проверочной матрицы немного больше). На практике применяются матрицы с большим количеством элементов — от 10 до 100 тысяч строк. Однако количество единиц в строке или в столбце остаётся достаточно малым, обычно меньшим 10. Замечено, что коды с тем же количеством элементов на строку или столбец, но с большим размером, обладают лучшими характеристиками.

Важной характеристикой матрицы LDPC-кода является отсутствие циклов определённого размера. Под циклом длины 4 понимают образование в проверочной матрице прямоугольника, в углах которого стоят единицы. Отсутствие цикла длины 4 можно также определить через скалярное произведение столбцов (или строк) матрицы. Если каждое попарное скалярное произведение всех столбцов (или строк) матрицы не более 1, это говорит об отсутствии цикла длины 4. Циклы большей длины (6, 8, 10 и т. д.) можно определить, если в проверочной матрице построить граф, вершинами которого являются единицы, а рёбра — все возможные соединения вершин, параллельные сторонам матрицы (то есть вертикальные или горизонтальные линии). Минимальный цикл в этом графе и будет минимальным циклом в проверочной матрице LDPC-кода. Очевидно, что цикл будет иметь длину как минимум 4, а не 3, так как рёбра графа должны быть параллельны сторонам матрицы. Вообще, любой цикл в этом графе будет иметь чётную длину, минимальный размер 4, а максимальный размер обычно не играет роли (хотя, очевидно, он не более, чем количество узлов в графе, то есть n×k).

Описание LDPC-кода возможно несколькими способами:

• проверочной матрицей
• двудольным графом
• другим графическим способом
• специальные способы

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

Способ задания кода проверочной матрицей является общепринятым для линейных кодов, когда каждая строка матрицы является элементом некоторого множества кодовых слов. Если все строки линейно-независимы, строки матрицы могут рассматриваться как базис множества всех кодовых векторов кода. Однако использование данного способа создаёт сложности для представления матрицы в памяти кодера — необходимо хранить все строки или столбцы матрицы в виде набора двоичных векторов, из-за чего размер матрицы становится равен <math>j \times k</math> бит.

Распространённым графическим способом является представление кода в виде двудольного графа. Сопоставим все <math>k</math> строк матрицы <math>k</math> нижним вершинам графа, а <math>n</math> столбцов — верхним, и соединим верхние и нижние вершины графа, если на пересечении соответствующих строк и столбцов стоят единицы.

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

Вводя дополнительные правила графического отображения и построения LDPC-кода, можно добиться, что в процессе построения код получит определённые свойства. Например, если использовать граф, вершинами которого являются только столбцы проверочной матрицы, а строки изображаются многогранниками, построенными на вершинах графа, то следование правилу «два многогранника не разделяют одно ребро» позволяет избавиться от циклов длины 4.

При использовании специальных процедур построения кода могут использоваться и свои способы представления, хранения и обработки (кодирования и декодирования).

Построение кода

В настоящее время используются два принципа построения проверочной матрицы кода. Первый основан на генерации начальной проверочной матрицы с помощью псевдослучайного генератора. Коды, полученные таким способом называют случайными (англ. random-like codes). Второй — использование специальных методов, основанных, например, на группах и конечных полях. Коды, полученные этими способами называют структурированными. Лучшие результаты по исправлению ошибок показывают именно случайные коды, однако структурированные коды позволяют использовать методы оптимизации процедур хранения, кодирования и декодирования, а также получать коды с более предсказуемыми характеристиками.

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

В 2003 году Джеймсом МакГованом и Робертом Вильямсоном был предложен способ удаления циклов из матрицы LDPC-кода, в связи с чем стало возможным в начале сгенерировать матрицу с заданными характеристиками (n, j, k), а затем удалить из неё циклы. Так происходит в схеме Озарова-Вайнера.

В 2007 году в журнале «IEEE Transactions on Information Threory» была опубликована статья об использовании конечных полей для построения квази-цикличных LDPC-кодов для каналов с аддитивным белым Гауссовым шумом и двоичных каналов со стиранием.

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

Как и для любого другого линейного кода, для декодирования используется свойство ортогональности порождающей и транспонированной проверочной матриц:

<math>G \odot H^T = 0</math>

где <math>G</math> — порождающая матрица, и <math>H</math> — проверочная. Тогда для каждого принятого без ошибок кодового слова выполняется отношение

<math>s = v \odot H^T = 0</math>,

а для принятого кодового слова с ошибкой:

<math>s = v \odot H^T \neq 0</math>,

где <math>v</math> — принятый вектор, <math>s</math> — синдром. В случае, если после умножения принятого кодового слова на транспонированную проверочную матрицу получается ноль, блок считается принятым без ошибок. В противном случае используются специальные методы для определения местоположения ошибки и её исправления. Для LDPC-кода стандартные способы исправления оказываются слишком трудоёмкими — их относят к классу NP-полных задач, что, учитывая большую длину блока, не может применяться на практике. Вместо них применяют метод вероятностного итеративного декодирования, исправляющую большую долю ошибок за границей половины кодового расстояния.

Рассмотрим симметричный канал без памяти со входом <math>\pm a</math> и аддитивным гауссовым шумом <math>\sigma ^2 = 1</math>. Для принятого кодового слова <math>y</math> нужно найти соответствующий наиболее вероятный вектор <math>x</math>, такой что

<math>H \odot x = 0 \mod 2</math>.

1. Определим

   <math>f_n^1 = {1 / \mathord{ \left( 1 + \exp \left( - 2ay_n / \mathord{\sigma^2} \right) \right) }}</math>;

   <math>f_n^0 = 1 - f_n^1</math>;

   где <math>y_n</math> — принятое значение n-го символа кодового слова (которое для данного канала имеет произвольное значение, обычно в рамках <math>\pm (a + 3 \sigma)</math>).

2. Будем использовать слово «бит» для обозначения отдельных элементов вектора <math>x</math>, и слово «проверка» для обозначения строк проверочной матрицы <math>H</math>. Обозначим через <math>N\left(m\right) \equiv \{ n:H_{nm} = 1\}</math> набор битов, которые будут участвовать в m-ой проверке. Аналогично, обозначим <math>M\left(n\right) \equiv \{ m:H_{nm} = 1\}</math> набор проверок, в которых участвует бит n. (То есть перечислим индексы ненулевых элементов для каждой строки и для каждого столбца проверочной матрицы <math>H</math>).
3. Инициализируем матрицы <math>q_{mn}^0</math> и <math>q_{mn}^1</math> значениями <math>f_n^0</math> и <math>f_n^1</math> соответственно
4. (Горизонтальный шаг)

   <math>\delta q_{mn} = q_{mn}^0 - q_{mn}^1</math>

   <math> \delta r_{mn} = \prod\limits_{n' \in N(m)\backslash n} {\delta q_{mn'} } </math>

   <math>r_{mn}^0 = {1 \over 2}\left( {1 + \delta r_{mn} } \right)</math>

   <math>r_{mn}^1 = {1 \over 2}\left( {1 - \delta r_{mn} } \right)</math>

5. (Вертикальный шаг)

   <math>q_{mn}^0 = \alpha_{mn} f_n^0 \prod\limits_{m' \in M\left( n \right)\backslash m} {r_{m'n}^0 } </math>

   <math>q_{mn}^1 = \alpha_{mn} f_n^1 \prod\limits_{m' \in M\left( n \right)\backslash m} {r_{m'n}^1 } </math>

   где для каждого <math>m</math> и <math>n</math> выбранное <math>\alpha_{mn}</math> даёт:

   <math>q_{mn}^0 + q_{mn}^1 = 1</math>

   Теперь также обновляем «псевдопостериорные вероятности» того, что биты вектора <math>x</math> принимают значения 0 или 1:

   <math>q_{n}^0 = \alpha_n f_n^0 \prod\limits_{m \in M\left( n \right)} {r_{mn}^0 }</math>

   <math>q_{n}^1 = \alpha_n f_n^1 \prod\limits_{m \in M\left( n \right)} {r_{mn}^1 }</math>

   Также, как и ранее, <math>\alpha_n</math> выбирается таким образом, что

   <math>q_{n}^0 + q_{n}^1 = 1</math>

Данные значения используются воссоздания вектора x. Если полученный вектор удовлетворяет <math>H \odot x = 0 \mod 2</math>, то алгоритм на этом прерывается, иначе повторяются горизонтальный и вертикальные шаги. Если же алгоритм продолжается до некоторого шага (например, 100), то он прерывается и блок объявляется принятым с ошибкой.

Известно, что данный алгоритм даёт точное значение вектора <math>x</math> (то есть, совпадающее с классическими способами), если проверочная матрица <math>H</math> не содержит циклов.

См. также

• Турбо-код
• Полярные коды

Отрывок, характеризующий Код с малой плотностью проверок на чётность

– Нет, еще не приезжал папа, – сказала Соня.
– Коко, ты приехал, поди ко мне, дружок! – сказал голос графини из гостиной. Николай подошел к матери, поцеловал ее руку и, молча подсев к ее столу, стал смотреть на ее руки, раскладывавшие карты. Из залы всё слышались смех и веселые голоса, уговаривавшие Наташу.
– Ну, хорошо, хорошо, – закричал Денисов, – теперь нечего отговариваться, за вами barcarolla, умоляю вас.
Графиня оглянулась на молчаливого сына.
– Что с тобой? – спросила мать у Николая.
– Ах, ничего, – сказал он, как будто ему уже надоел этот всё один и тот же вопрос.
– Папенька скоро приедет?
– Я думаю.
«У них всё то же. Они ничего не знают! Куда мне деваться?», подумал Николай и пошел опять в залу, где стояли клавикорды.
Соня сидела за клавикордами и играла прелюдию той баркароллы, которую особенно любил Денисов. Наташа собиралась петь. Денисов восторженными глазами смотрел на нее.
Николай стал ходить взад и вперед по комнате.
«И вот охота заставлять ее петь? – что она может петь? И ничего тут нет веселого», думал Николай.
Соня взяла первый аккорд прелюдии.
«Боже мой, я погибший, я бесчестный человек. Пулю в лоб, одно, что остается, а не петь, подумал он. Уйти? но куда же? всё равно, пускай поют!»
Николай мрачно, продолжая ходить по комнате, взглядывал на Денисова и девочек, избегая их взглядов.
«Николенька, что с вами?» – спросил взгляд Сони, устремленный на него. Она тотчас увидала, что что нибудь случилось с ним.
Николай отвернулся от нее. Наташа с своею чуткостью тоже мгновенно заметила состояние своего брата. Она заметила его, но ей самой так было весело в ту минуту, так далека она была от горя, грусти, упреков, что она (как это часто бывает с молодыми людьми) нарочно обманула себя. Нет, мне слишком весело теперь, чтобы портить свое веселье сочувствием чужому горю, почувствовала она, и сказала себе:
«Нет, я верно ошибаюсь, он должен быть весел так же, как и я». Ну, Соня, – сказала она и вышла на самую середину залы, где по ее мнению лучше всего был резонанс. Приподняв голову, опустив безжизненно повисшие руки, как это делают танцовщицы, Наташа, энергическим движением переступая с каблучка на цыпочку, прошлась по середине комнаты и остановилась.
«Вот она я!» как будто говорила она, отвечая на восторженный взгляд Денисова, следившего за ней.
«И чему она радуется! – подумал Николай, глядя на сестру. И как ей не скучно и не совестно!» Наташа взяла первую ноту, горло ее расширилось, грудь выпрямилась, глаза приняли серьезное выражение. Она не думала ни о ком, ни о чем в эту минуту, и из в улыбку сложенного рта полились звуки, те звуки, которые может производить в те же промежутки времени и в те же интервалы всякий, но которые тысячу раз оставляют вас холодным, в тысячу первый раз заставляют вас содрогаться и плакать.
Наташа в эту зиму в первый раз начала серьезно петь и в особенности оттого, что Денисов восторгался ее пением. Она пела теперь не по детски, уж не было в ее пеньи этой комической, ребяческой старательности, которая была в ней прежде; но она пела еще не хорошо, как говорили все знатоки судьи, которые ее слушали. «Не обработан, но прекрасный голос, надо обработать», говорили все. Но говорили это обыкновенно уже гораздо после того, как замолкал ее голос. В то же время, когда звучал этот необработанный голос с неправильными придыханиями и с усилиями переходов, даже знатоки судьи ничего не говорили, и только наслаждались этим необработанным голосом и только желали еще раз услыхать его. В голосе ее была та девственная нетронутость, то незнание своих сил и та необработанная еще бархатность, которые так соединялись с недостатками искусства пенья, что, казалось, нельзя было ничего изменить в этом голосе, не испортив его.
«Что ж это такое? – подумал Николай, услыхав ее голос и широко раскрывая глаза. – Что с ней сделалось? Как она поет нынче?» – подумал он. И вдруг весь мир для него сосредоточился в ожидании следующей ноты, следующей фразы, и всё в мире сделалось разделенным на три темпа: «Oh mio crudele affetto… [О моя жестокая любовь…] Раз, два, три… раз, два… три… раз… Oh mio crudele affetto… Раз, два, три… раз. Эх, жизнь наша дурацкая! – думал Николай. Всё это, и несчастье, и деньги, и Долохов, и злоба, и честь – всё это вздор… а вот оно настоящее… Hy, Наташа, ну, голубчик! ну матушка!… как она этот si возьмет? взяла! слава Богу!» – и он, сам не замечая того, что он поет, чтобы усилить этот si, взял втору в терцию высокой ноты. «Боже мой! как хорошо! Неужели это я взял? как счастливо!» подумал он.
О! как задрожала эта терция, и как тронулось что то лучшее, что было в душе Ростова. И это что то было независимо от всего в мире, и выше всего в мире. Какие тут проигрыши, и Долоховы, и честное слово!… Всё вздор! Можно зарезать, украсть и всё таки быть счастливым…


Давно уже Ростов не испытывал такого наслаждения от музыки, как в этот день. Но как только Наташа кончила свою баркароллу, действительность опять вспомнилась ему. Он, ничего не сказав, вышел и пошел вниз в свою комнату. Через четверть часа старый граф, веселый и довольный, приехал из клуба. Николай, услыхав его приезд, пошел к нему.
– Ну что, повеселился? – сказал Илья Андреич, радостно и гордо улыбаясь на своего сына. Николай хотел сказать, что «да», но не мог: он чуть было не зарыдал. Граф раскуривал трубку и не заметил состояния сына.
«Эх, неизбежно!» – подумал Николай в первый и последний раз. И вдруг самым небрежным тоном, таким, что он сам себе гадок казался, как будто он просил экипажа съездить в город, он сказал отцу.
– Папа, а я к вам за делом пришел. Я было и забыл. Мне денег нужно.
– Вот как, – сказал отец, находившийся в особенно веселом духе. – Я тебе говорил, что не достанет. Много ли?
– Очень много, – краснея и с глупой, небрежной улыбкой, которую он долго потом не мог себе простить, сказал Николай. – Я немного проиграл, т. е. много даже, очень много, 43 тысячи.
– Что? Кому?… Шутишь! – крикнул граф, вдруг апоплексически краснея шеей и затылком, как краснеют старые люди.
– Я обещал заплатить завтра, – сказал Николай.
– Ну!… – сказал старый граф, разводя руками и бессильно опустился на диван.
– Что же делать! С кем это не случалось! – сказал сын развязным, смелым тоном, тогда как в душе своей он считал себя негодяем, подлецом, который целой жизнью не мог искупить своего преступления. Ему хотелось бы целовать руки своего отца, на коленях просить его прощения, а он небрежным и даже грубым тоном говорил, что это со всяким случается.
Граф Илья Андреич опустил глаза, услыхав эти слова сына и заторопился, отыскивая что то.
– Да, да, – проговорил он, – трудно, я боюсь, трудно достать…с кем не бывало! да, с кем не бывало… – И граф мельком взглянул в лицо сыну и пошел вон из комнаты… Николай готовился на отпор, но никак не ожидал этого.
– Папенька! па…пенька! – закричал он ему вслед, рыдая; простите меня! – И, схватив руку отца, он прижался к ней губами и заплакал.

В то время, как отец объяснялся с сыном, у матери с дочерью происходило не менее важное объяснение. Наташа взволнованная прибежала к матери.
– Мама!… Мама!… он мне сделал…
– Что сделал?
– Сделал, сделал предложение. Мама! Мама! – кричала она. Графиня не верила своим ушам. Денисов сделал предложение. Кому? Этой крошечной девочке Наташе, которая еще недавно играла в куклы и теперь еще брала уроки.
– Наташа, полно, глупости! – сказала она, еще надеясь, что это была шутка.
– Ну вот, глупости! – Я вам дело говорю, – сердито сказала Наташа. – Я пришла спросить, что делать, а вы мне говорите: «глупости»…
Графиня пожала плечами.
– Ежели правда, что мосьё Денисов сделал тебе предложение, то скажи ему, что он дурак, вот и всё.
– Нет, он не дурак, – обиженно и серьезно сказала Наташа.
– Ну так что ж ты хочешь? Вы нынче ведь все влюблены. Ну, влюблена, так выходи за него замуж! – сердито смеясь, проговорила графиня. – С Богом!
– Нет, мама, я не влюблена в него, должно быть не влюблена в него.
– Ну, так так и скажи ему.
– Мама, вы сердитесь? Вы не сердитесь, голубушка, ну в чем же я виновата?
– Нет, да что же, мой друг? Хочешь, я пойду скажу ему, – сказала графиня, улыбаясь.
– Нет, я сама, только научите. Вам всё легко, – прибавила она, отвечая на ее улыбку. – А коли бы видели вы, как он мне это сказал! Ведь я знаю, что он не хотел этого сказать, да уж нечаянно сказал.
– Ну всё таки надо отказать.
– Нет, не надо. Мне так его жалко! Он такой милый.
– Ну, так прими предложение. И то пора замуж итти, – сердито и насмешливо сказала мать.
– Нет, мама, мне так жалко его. Я не знаю, как я скажу.
– Да тебе и нечего говорить, я сама скажу, – сказала графиня, возмущенная тем, что осмелились смотреть, как на большую, на эту маленькую Наташу.
– Нет, ни за что, я сама, а вы слушайте у двери, – и Наташа побежала через гостиную в залу, где на том же стуле, у клавикорд, закрыв лицо руками, сидел Денисов. Он вскочил на звук ее легких шагов.
– Натали, – сказал он, быстрыми шагами подходя к ней, – решайте мою судьбу. Она в ваших руках!
– Василий Дмитрич, мне вас так жалко!… Нет, но вы такой славный… но не надо… это… а так я вас всегда буду любить.
Денисов нагнулся над ее рукою, и она услыхала странные, непонятные для нее звуки. Она поцеловала его в черную, спутанную, курчавую голову. В это время послышался поспешный шум платья графини. Она подошла к ним.
– Василий Дмитрич, я благодарю вас за честь, – сказала графиня смущенным голосом, но который казался строгим Денисову, – но моя дочь так молода, и я думала, что вы, как друг моего сына, обратитесь прежде ко мне. В таком случае вы не поставили бы меня в необходимость отказа.
– Г'афиня, – сказал Денисов с опущенными глазами и виноватым видом, хотел сказать что то еще и запнулся.
Наташа не могла спокойно видеть его таким жалким. Она начала громко всхлипывать.
– Г'афиня, я виноват перед вами, – продолжал Денисов прерывающимся голосом, – но знайте, что я так боготво'ю вашу дочь и всё ваше семейство, что две жизни отдам… – Он посмотрел на графиню и, заметив ее строгое лицо… – Ну п'ощайте, г'афиня, – сказал он, поцеловал ее руку и, не взглянув на Наташу, быстрыми, решительными шагами вышел из комнаты.

На другой день Ростов проводил Денисова, который не хотел более ни одного дня оставаться в Москве. Денисова провожали у цыган все его московские приятели, и он не помнил, как его уложили в сани и как везли первые три станции.
После отъезда Денисова, Ростов, дожидаясь денег, которые не вдруг мог собрать старый граф, провел еще две недели в Москве, не выезжая из дому, и преимущественно в комнате барышень.
Соня была к нему нежнее и преданнее чем прежде. Она, казалось, хотела показать ему, что его проигрыш был подвиг, за который она теперь еще больше любит его; но Николай теперь считал себя недостойным ее.
Он исписал альбомы девочек стихами и нотами, и не простившись ни с кем из своих знакомых, отослав наконец все 43 тысячи и получив росписку Долохова, уехал в конце ноября догонять полк, который уже был в Польше.



После своего объяснения с женой, Пьер поехал в Петербург. В Торжке на cтанции не было лошадей, или не хотел их смотритель. Пьер должен был ждать. Он не раздеваясь лег на кожаный диван перед круглым столом, положил на этот стол свои большие ноги в теплых сапогах и задумался.
– Прикажете чемоданы внести? Постель постелить, чаю прикажете? – спрашивал камердинер.
Пьер не отвечал, потому что ничего не слыхал и не видел. Он задумался еще на прошлой станции и всё продолжал думать о том же – о столь важном, что он не обращал никакого .внимания на то, что происходило вокруг него. Его не только не интересовало то, что он позже или раньше приедет в Петербург, или то, что будет или не будет ему места отдохнуть на этой станции, но всё равно было в сравнении с теми мыслями, которые его занимали теперь, пробудет ли он несколько часов или всю жизнь на этой станции.
Смотритель, смотрительша, камердинер, баба с торжковским шитьем заходили в комнату, предлагая свои услуги. Пьер, не переменяя своего положения задранных ног, смотрел на них через очки, и не понимал, что им может быть нужно и каким образом все они могли жить, не разрешив тех вопросов, которые занимали его. А его занимали всё одни и те же вопросы с самого того дня, как он после дуэли вернулся из Сокольников и провел первую, мучительную, бессонную ночь; только теперь в уединении путешествия, они с особенной силой овладели им. О чем бы он ни начинал думать, он возвращался к одним и тем же вопросам, которых он не мог разрешить, и не мог перестать задавать себе. Как будто в голове его свернулся тот главный винт, на котором держалась вся его жизнь. Винт не входил дальше, не выходил вон, а вертелся, ничего не захватывая, всё на том же нарезе, и нельзя было перестать вертеть его.
Вошел смотритель и униженно стал просить его сиятельство подождать только два часика, после которых он для его сиятельства (что будет, то будет) даст курьерских. Смотритель очевидно врал и хотел только получить с проезжего лишние деньги. «Дурно ли это было или хорошо?», спрашивал себя Пьер. «Для меня хорошо, для другого проезжающего дурно, а для него самого неизбежно, потому что ему есть нечего: он говорил, что его прибил за это офицер. А офицер прибил за то, что ему ехать надо было скорее. А я стрелял в Долохова за то, что я счел себя оскорбленным, а Людовика XVI казнили за то, что его считали преступником, а через год убили тех, кто его казнил, тоже за что то. Что дурно? Что хорошо? Что надо любить, что ненавидеть? Для чего жить, и что такое я? Что такое жизнь, что смерть? Какая сила управляет всем?», спрашивал он себя. И не было ответа ни на один из этих вопросов, кроме одного, не логического ответа, вовсе не на эти вопросы. Ответ этот был: «умрешь – всё кончится. Умрешь и всё узнаешь, или перестанешь спрашивать». Но и умереть было страшно.
Торжковская торговка визгливым голосом предлагала свой товар и в особенности козловые туфли. «У меня сотни рублей, которых мне некуда деть, а она в прорванной шубе стоит и робко смотрит на меня, – думал Пьер. И зачем нужны эти деньги? Точно на один волос могут прибавить ей счастья, спокойствия души, эти деньги? Разве может что нибудь в мире сделать ее и меня менее подверженными злу и смерти? Смерть, которая всё кончит и которая должна притти нынче или завтра – всё равно через мгновение, в сравнении с вечностью». И он опять нажимал на ничего не захватывающий винт, и винт всё так же вертелся на одном и том же месте.
Слуга его подал ему разрезанную до половины книгу романа в письмах m mе Suza. [мадам Сюза.] Он стал читать о страданиях и добродетельной борьбе какой то Аmelie de Mansfeld. [Амалии Мансфельд.] «И зачем она боролась против своего соблазнителя, думал он, – когда она любила его? Не мог Бог вложить в ее душу стремления, противного Его воле. Моя бывшая жена не боролась и, может быть, она была права. Ничего не найдено, опять говорил себе Пьер, ничего не придумано. Знать мы можем только то, что ничего не знаем. И это высшая степень человеческой премудрости».
Всё в нем самом и вокруг него представлялось ему запутанным, бессмысленным и отвратительным. Но в этом самом отвращении ко всему окружающему Пьер находил своего рода раздражающее наслаждение.
– Осмелюсь просить ваше сиятельство потесниться крошечку, вот для них, – сказал смотритель, входя в комнату и вводя за собой другого, остановленного за недостатком лошадей проезжающего. Проезжающий был приземистый, ширококостый, желтый, морщинистый старик с седыми нависшими бровями над блестящими, неопределенного сероватого цвета, глазами.