Очередь FIFO (First In, First Out) представляет собой циклический буфер, где будут храниться помещаемые в очередь данные. Есть два указателя: указатель на «голову» очереди (head) и указатель на «хвост» очереди (tail).
Новый записываемый элемент помещается в ячейку, на которую указывает head, затем этот указатель перемещается на следующую ячейку памяти буфера.
Выбираются элементы из очереди по указателю tail, после того, как элемент выбран из очереди, указатель tail так же передвигается вперед к следующей ячейке.
Обычно глубина FIFO и разрядность указателей являются числами степени двойки. Например, если разрядность указателей head и tail – это 8, то глубина FIFO будет 256 элементов.
Цикличность буфера обеспечивается автоматически. При последовательном увеличении значения указателя однажды возникнает перенос, а сам указатель при этом обнуляется (после указателя 255 его следующее значение будет 0).
Теперь, когда мы знаем, что есть два указателя, легко определить всякие информационные сигналы:
- FIFO пусто, если значения указателей «голова» и «хвост» равны.
- Число элементов хранимых в FIFO можно вычислить отняв от значения «головы» значение указателя «хвоста». Если получится отрицательное число, то нужно еще прибавить глубину FIFO.
- FIFO полное, если число хранимых элементов на единицу меньше, чем глубина FIFO.
Возможно, последнее утверждение нуждается в пояснении. Например, глубина FIFO 256 элементов. Мы запишем в него 255 элементов, но читать из FIFO пока не будем. Тогда «голова»=255, а «хвост»=0. Сейчас FIFO полное. Если в него записать еще один элемент, то значение «головы» станет 0 (возникает перенос) и получится, что и «голова» и «хвост» становятся одинаковыми и равными нулю. Все, FIFO опять стало пустым? Конечно, это ошибка логики.
Нельзя допускать запись в полное FIFO и чтение/выборку элемента из пустого FIFO.
Все вышеописанное прекрасно, но что делать, если запись и чтение происходят с использованием разных тактовых частот, если FIFO асинхронное? Мы не можем на прямую сравнивать или делать какие-то арифметические операции с указателями «голова» и «хвост», так как в этом случае они храняться в разных клоковых доменах (clock domains).
Просто пересинхронизировать группу (8-ми битные счетчики указателей голова и хвост) сигналов в другой домен не есть хороший вариант, как было уже ранее показано в другой статье. Главная проблема здесь – не все биты шины могут перейти в другой клоковый домен одновременно, а значит двоичное число на шине может быть искажено.
С другой стороны, понятно, что и «хвост» и «голова» могут изменяться только на единицу за один раз. То есть они считают последовательно. Этот факт как раз и делает возможным использование специальных счетчиков - счетчиков Грея.
Код Грея — специальная система счисления, в которой два соседних значения различаются только в одном разряде.
Вот пример трехбитных кодов Грея. Слева в таблице значения обычного двоичного счетчика, а справа значения из счетчика Грея.
|
000 |
000 |
Методика использования кодов Грея может быть следующая. Значение счетчика указателя, например, головы FIFO перекодируется в код Грея и пересекает клоковый домен с помощью группы синхронизаторов (каждый – это два последовательных триггера). При этом, как мы знаем, не все биты могут быть зафиксированы верно: в новом клоковом домене в некоторых битах зафиксируются новые значения числа на шине, а в некоторых – старые значения. Однако, для кода Грея изменения в соседних числах счетчика происходят только в одном бите, значит только в одном бите и может произойти коллизия. Только один изменяющийся сейчас бит может быть принят не верно. В этом случае принимающий домен просто считает предыдущее число на шине, а верное, следующее число он считает на следующем такте своей частоты. Такая ошибка даже и ошибкой не считается, ведь она не приводит к аварии FIFO.
Принятый код Грея может быть перекодирован обратно в обычную двоичную систему счисления и тут уже мы имеем верное значение обоих указателей в одном клоковом домене. Теперь можно их сравнивать, вычислять число элементов в FIFO и так далее.
В принципе, FIFO может изначально держать указатели «головы» и «хвоста» в кодах Грея.
Вообще использование кодов Грея в асинхронных FIFO очень распространено, так как действительно позволяет решить проблему пересечения клокового домена для потока данных.
Подробнее...