Равномерный износ битов, Алгоритм представления числа в регистре Опции

[vazhko]

Прошу помощи в следующей задаче.
Имеем массив энергонезависимой памяти (EEPROM) с ограниченным количеством перезаписи битов(число перезаписей около 1Е6).
Надо каждый раз писать в эту память значения счетчика при его инкременте. Допустим счетчик 32-битный. При инкременте на единицу, младший бит регистра изменяется настолько часто, что можно получить его неработоспособность всего регистра еще до того, как он заполнится. Соответственно, старший бит измениться всего один раз. Существует ли алгоритм такого представления числа(прямой и обратный, на подобие кода Грея), чтобы при последовательном инкременте до заполнения регистра, количество модификаций битов в регистре была примерно равна и минимальна. Разрядность преставления может быть больше разрядности самого числа.

[Polaris]

Прошу помощи в следующей задаче.
Имеем массив энергонезависимой памяти (EEPROM) с ограниченным количеством перезаписи битов(число перезаписей около 1Е6).
Надо каждый раз писать в эту память значения счетчика при его инкременте. Допустим счетчик 32-битный. При инкременте на единицу, младший бит регистра изменяется настолько часто, что можно получить его неработоспособность всего регистра еще до того, как он заполнится. Соответственно, старший бит измениться всего один раз. Существует ли алгоритм такого представления числа(прямой и обратный, на подобие кода Грея), чтобы при последовательном инкременте до заполнения регистра, количество модификаций битов в регистре была примерно равна и минимальна. Разрядность преставления может быть больше разрядности самого числа.

Код Джонсона?

[MrYuran]

00000001
00000011
00000111
00001111
00011111
00111111
01111111
11111111
00000010
00000110
00001110
00011110
...
Ну вот как-то так...
закрашивать биты можно по очереди без стирания.
Только наверно в ЕЕПРОМ инверсно будет. То есть закрашивание нулями.

[vazhko]

Polaris, MrYuran.
Спасибо большое, по-моему самое оно.
Буду думать о реализации алгоритма.

[Herz]

00000001
00000011
00000111
00001111
00011111
00111111
01111111
11111111
00000010
00000110
00001110
00011110
...

11111111
11111110
11111100
....
?

[alexander55]

11111111
11111110
11111100
....
?

Да, он так и предложил (инверсно).
Только, уточню
11111111
11111110
11111101
....

[Herz]

Да, он так и предложил (инверсно).
Только, уточню
11111111
11111110
11111101
....

нет, так два бита за раз меняются, а это нехорошо.

[scifi]

Имеем массив энергонезависимой памяти (EEPROM) с ограниченным количеством перезаписи битов(число перезаписей около 1Е6).

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

[alexander55]

нет, так два бита за раз меняются, а это нехорошо.

Вы правы, я сразу не обратил внимание.

А я думал, что у EEPROM считается ресурс байтов, а не битов. То есть при перезаписи байт стирается целиком.

По физике - это количество перезарядов, которые надо минимизировать.

[vazhko]

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

1 Код Джонсона не подошел: он слишком избыточный. На 8 битах получается 37 комбинаций.

2 Есть разновидности кода Грея. В часности, balanced Gray code, который бы идеально подошел для данной задачи. Но как его генерировать компактным кодом не понятно, и по всей видимости, задача совсем не простая. В случае с 8-ми битным счетчиком все просто - можно было бы брать значения из заранее составленой таблицы, а вот как быть с 16 и 32 разрядными счетчиками? Может быть кто-то реализовывал?

[Herz]

Из Википедии:

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

unsigned int grayencode(unsigned int g)
{
return g ^ (g >> 1);
}

Обратный алгоритм (преобразование из кода Грея в двоичную систему счисления):

unsigned int graydecode(unsigned int gray)
{
unsigned int bin;
for (bin = 0; gray; gray >>= 1) {bin ^= gray;}
return bin;
}

[vazhko]

Из Википедии:

Это стандартный код Грея. Нужен сбалансированный код Грея.

[Herz]

Это стандартный код Грея. Нужен сбалансированный код Грея.

Честно говоря, не знаю их отличий. Насколько он эффективнее стандартного в рассматриваемом смысле? Может, выигрыш не столь значителен, чтобы усложнять реализацию?

[НЕХ]

патент в помощь

Прикрепленные файлы

 US_6084935.pdf ( 56.06 килобайт ) Кол-во скачиваний: 212

 

[vazhko]

Честно говоря, не знаю их отличий. Насколько он эффективнее стандартного в рассматриваемом смысле? Может, выигрыш не столь значителен, чтобы усложнять реализацию?

Действительно, выигрыш получается небольшой (в 2 раза потив стандартного), но все же... Мне кажется, что как все гениальное, реализация алгоритма может оказаться простой.

патент в помощь

Вот за это огромное спасибо! Буду курить изучать.

[yafalschivii]

всё и в правду, покажется просто, если поймёшь код Бина

[НЕХ]

только в этом патенте ругают и этот алгоритм...
а вот приветы от атмел, интел и микрософт.
курите на здоровье !
только результаты на общее обсуждение !

Прикрепленные файлы

 US6792065.pdf ( 129.8 килобайт ) Кол-во скачиваний: 127
 US7065607.pdf ( 129.3 килобайт ) Кол-во скачиваний: 100
 US6249562.pdf ( 172.01 килобайт ) Кол-во скачиваний: 152

 

[vazhko]

только в этом патенте ругают и этот алгоритм...
а вот приветы от атмел, интел и микрософт.
курите на здоровье !
только результаты на общее обсуждение !

Еще раз спасибо. Отпишусь обязательно, только закончу предыдущий проект.

[НЕХ]

не копая глубоко, имею вопросы...
на ресурс памяти что оказывает большее негативное действие :
стирание или запись "0"?
при стирании подвергаются ли износу биты = "1" ?
всегда ли предшествует записи операция стирания ?
стирание едино для байта или индивидуально для каждого бита, в зависимости от его состояния ?
имеет ли смысл использовать вместо битов целиком байты ?( прописывать 00h или FFh, а при анализе сравнивать кол-во 0 и 1 в байте и принимать решение по большинству)
ущербная ячейка куда будет склонять - к 0 или 1 ?

[vazhko]

имеет ли смысл использовать вместо битов целиком байты ?( прописывать 00h или FFh, а при анализе сравнивать кол-во 0 и 1 в байте и принимать решение по большинству)
ущербная ячейка куда будет склонять - к 0 или 1 ?

Совершенно верно. Так и планирую сделать. Не вдаваясь в подробности функционирования EEPROM конкретного взятого контроллера. Обращение (запись/чтение/ стирание) к ячейке EEPROM происходит побайтно. Стирание перед записью обязательно. Какие операции оказывают негативное воздействие не знаю. Надо читать теорию.

[НЕХ]

а попадались ли рекомендации непосредственно производителей контроллеров на эту тему ?

[vazhko]

а попадались ли рекомендации непосредственно производителей контроллеров на эту тему ?

Не попадались, по крайней мере у Микрочипа.

[atlantic]

Прошу помощи в следующей задаче.
Имеем массив энергонезависимой памяти (EEPROM) с ограниченным количеством перезаписи битов(число перезаписей около 1Е6).
Надо каждый раз писать в эту память значения счетчика при его инкременте. Допустим счетчик 32-битный. При инкременте на единицу, младший бит регистра изменяется настолько часто, что можно получить его неработоспособность всего регистра еще до того, как он заполнится. Соответственно, старший бит измениться всего один раз. Существует ли алгоритм такого представления числа(прямой и обратный, на подобие кода Грея), чтобы при последовательном инкременте до заполнения регистра, количество модификаций битов в регистре была примерно равна и минимальна. Разрядность преставления может быть больше разрядности самого числа.

У вас в вопросе уже готовый ответ, как биты не переставляй а гарантированный срок службы EEPROM 1-миллион циклов записей. Вам надо определится как часто будет запись, а то

изменяется настолько часто что можно получить его неработоспособность

это не цифры, например 1 раз в секунду, или сколько ?

если речь идет о количествах циклов записи более 10 тысяч в год, то для таких целей вероятно следует использовать другой тип памяти - энергонезависимое ОЗУ, например ibutton, срок службы ~10 лет,если мало то по прошествии срока, стоит обновить девайс :-)

[vazhko]

У вас в вопросе уже готовый ответ, как биты не переставляй а гарантированный срок службы EEPROM 1-миллион циклов записей.

Не всего EEPROM, а стираний/записей в конкретный регистр. Причем под 1 бит, будет отводится 1 байт.

изменяется настолько часто что можно получить его неработоспособность

это не цифры, например 1 раз в секунду, или сколько ?

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

если речь идет о количествах циклов записи более 10 тысяч в год, то для таких целей вероятно следует использовать другой тип памяти - энергонезависимое ОЗУ, например ibutton, срок службы ~10 лет,если мало то по прошествии срока, стоит обновить девайс :-)

Есть разные хардварные решения данной задачи и попроще, чем применение энергонезависимого ОЗУ. Но, в данном конкретном случае, интересна именно программная реализация, т.к. задача не с нуля - железо УЖЕ есть.

[alexander55]

не копая глубоко, имею вопросы...
на ресурс памяти что оказывает большее негативное действие :
стирание или запись "0"?
при стирании подвергаются ли износу биты = "1" ?
всегда ли предшествует записи операция стирания ?
стирание едино для байта или индивидуально для каждого бита, в зависимости от его состояния ?
имеет ли смысл использовать вместо битов целиком байты ?( прописывать 00h или FFh, а при анализе сравнивать кол-во 0 и 1 в байте и принимать решение по большинству)
ущербная ячейка куда будет склонять - к 0 или 1 ?

Для Flash памяти стирание приводит к установке в 1. Запись осуществляет установку в 0.
Для ресурса имеет значение количество стираний.
Для EEPROM производится запись и поэтому разницы нет. Для ресурса имеет значение изменение состояния.
МСМ.

[atlantic]

Не всего EEPROM, а стираний/записей в конкретный регистр. Причем под 1 бит, будет отводится 1 байт.

это не цифры, например 1 раз в секунду, или сколько ?

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

Есть разные хардварные решения данной задачи и попроще, чем применение энергонезависимого ОЗУ. Но, в данном конкретном случае, интересна именно программная реализация, т.к. задача не с нуля - железо УЖЕ есть.

И всетаки, какой EEPROM и сколько(в абсолютных величинах- разы :) циклов записи в год предполагаете?

Может чего-то я не понимаю ? Есть даташит на девайс, там оговорено максимальное кол-во циклов, причем не очень четко, т.е. для своих целей надо брать с запасом. Как бы биты не переставлялись, а операции записи от этого не уменьшатся(в кол-ве раз) так ведь, или я что то не понял? Как внутри работает EEPROM четко не специфицируется, и расчитывать на то, что при записи одинаковых значений несколько раз подряд, будь то хоть 0 хоть FF, общее кол-во допустимых(при которых нет отказов) циклов записи уменьшится нет никаких оснований. Есть физические процессы которые влияют на отказы при записи, и они зависят от температуры окружающей среды, напряжений питаний, технологии по которой изготовлена EEPROM. В даташите приведен усредненный параметр работы без отказов. Самый надежный способ работать без отказов - это придерживаться параметров даташит с запасом.

[vazhko]

Может чего-то я не понимаю ? Есть даташит на девайс, там оговорено максимальное кол-во циклов, причем не очень четко, т.е. для своих целей надо брать с запасом. Как бы биты не переставлялись, а операции записи от этого не уменьшатся(в кол-ве раз) так ведь, или я что то не понял? Как внутри работает EEPROM четко не специфицируется, и расчитывать на то, что при записи одинаковых значений несколько раз подряд, будь то хоть 0 хоть FF, общее кол-во допустимых(при которых нет отказов) циклов записи уменьшится нет никаких оснований.

Дык, в том и прикол, что перезаписываюся только изменившиеся биты. И только один (в идеале) за инкремент. Нет смысла перезаписывать ту позицию, которую не надо менять.

Сообщение отредактировал vazhko - Nov 6 2008, 10:08

[scifi]

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

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

[GoG]

А наверное енто всё так просто не просчитать..
Как я понял в ПЗУ организуется просто последовательный счётчик
Если места в EEPROMe много, что можно под бит использовать байт, то можно поступить и проще:
писать "прямым" и удобным для использования двоичным кодом и байт пряма в свой байт, но просто переносить весь (или начиная с младших байтов) в другие ячейки, а ячейки с выработанным ресурсов просто обходить.
В этом деле можно смотреть на какой-нибудь большой разряд (например 18) и по его сбросу делать перенос всего счётчика (или его части) в другой набор ячеек, отмечая это смещение в специальной ячейке.
вот и всё

Да. Есть подозрение, что часто используемые ячейки не дадут паспортной длительности хранения (а ещё перепады температуры и т.п.).