Прошу помощи в следующей задаче.
Имеем массив энергонезависимой памяти (EEPROM) с ограниченным количеством перезаписи битов(число перезаписей около 1Е6).
Надо каждый раз писать в эту память значения счетчика при его инкременте. Допустим счетчик 32-битный. При инкременте на единицу, младший бит регистра изменяется настолько часто, что можно получить его неработоспособность всего регистра еще до того, как он заполнится. Соответственно, старший бит измениться всего один раз. Существует ли алгоритм такого представления числа(прямой и обратный, на подобие кода Грея), чтобы при последовательном инкременте до заполнения регистра, количество модификаций битов в регистре была примерно равна и минимальна. Разрядность преставления может быть больше разрядности самого числа.
Полная версия этой страницы: Равномерный износ битов
Форум разработчиков электроники ELECTRONIX.ru > Cистемный уровень проектирования > Математика и Физика
Цитата(vazhko @ Oct 29 2008, 14:30) 
Прошу помощи в следующей задаче.
Имеем массив энергонезависимой памяти (EEPROM) с ограниченным количеством перезаписи битов(число перезаписей около 1Е6).
Надо каждый раз писать в эту память значения счетчика при его инкременте. Допустим счетчик 32-битный. При инкременте на единицу, младший бит регистра изменяется настолько часто, что можно получить его неработоспособность всего регистра еще до того, как он заполнится. Соответственно, старший бит измениться всего один раз. Существует ли алгоритм такого представления числа(прямой и обратный, на подобие кода Грея), чтобы при последовательном инкременте до заполнения регистра, количество модификаций битов в регистре была примерно равна и минимальна. Разрядность преставления может быть больше разрядности самого числа.
Имеем массив энергонезависимой памяти (EEPROM) с ограниченным количеством перезаписи битов(число перезаписей около 1Е6).
Надо каждый раз писать в эту память значения счетчика при его инкременте. Допустим счетчик 32-битный. При инкременте на единицу, младший бит регистра изменяется настолько часто, что можно получить его неработоспособность всего регистра еще до того, как он заполнится. Соответственно, старший бит измениться всего один раз. Существует ли алгоритм такого представления числа(прямой и обратный, на подобие кода Грея), чтобы при последовательном инкременте до заполнения регистра, количество модификаций битов в регистре была примерно равна и минимальна. Разрядность преставления может быть больше разрядности самого числа.
Код Джонсона?
00000001
00000011
00000111
00001111
00011111
00111111
01111111
11111111
00000010
00000110
00001110
00011110
...
Ну вот как-то так...
закрашивать биты можно по очереди без стирания.
Только наверно в ЕЕПРОМ инверсно будет. То есть закрашивание нулями.
00000011
00000111
00001111
00011111
00111111
01111111
11111111
00000010
00000110
00001110
00011110
...
Ну вот как-то так...
закрашивать биты можно по очереди без стирания.
Только наверно в ЕЕПРОМ инверсно будет. То есть закрашивание нулями.
Polaris, MrYuran.
Спасибо большое, по-моему самое оно.
Буду думать о реализации алгоритма.
Спасибо большое, по-моему самое оно.
Буду думать о реализации алгоритма.
Цитата(MrYuran @ Oct 29 2008, 14:48)
00000001
00000011
00000111
00001111
00011111
00111111
01111111
11111111
00000010
00000110
00001110
00011110
...
00000011
00000111
00001111
00011111
00111111
01111111
11111111
00000010
00000110
00001110
00011110
...
11111111
11111110
11111100
....
?
Цитата(Herz @ Oct 29 2008, 16:32)
11111111
11111110
11111100
....
?
11111110
11111100
....
?
Да, он так и предложил (инверсно).
Только, уточню
11111111
11111110
11111101
....
Цитата(alexander55 @ Oct 29 2008, 15:36)
Да, он так и предложил (инверсно).
Только, уточню
11111111
11111110
11111101
....
Только, уточню
11111111
11111110
11111101
....
нет, так два бита за раз меняются, а это нехорошо.
Цитата(vazhko @ Oct 29 2008, 15:30)
Имеем массив энергонезависимой памяти (EEPROM) с ограниченным количеством перезаписи битов(число перезаписей около 1Е6).
А я думал, что у EEPROM считается ресурс байтов, а не битов. То есть при перезаписи байт стирается целиком.
Если так, что нужна такая кодировка счётчика, чтобы при последовательных приращениях все байты счётчика изменялись с равной частотой. Я такую схему реализовывал. Причём описание нашёл в каком-то патенте США. Идея очевидная, но всё равно приятно, когда всё разжёвано. Жаль, не могу отыскать номер того патента...
Цитата(Herz @ Oct 29 2008, 19:25)
нет, так два бита за раз меняются, а это нехорошо.
Вы правы, я сразу не обратил внимание.
Цитата(scifi @ Oct 29 2008, 19:45)
А я думал, что у EEPROM считается ресурс байтов, а не битов. То есть при перезаписи байт стирается целиком.
По физике - это количество перезарядов, которые надо минимизировать.
Поскольку несколько последних постов пропали в связи с проблемами на форуме, напомню вкратце.
1 Код Джонсона не подошел: он слишком избыточный. На 8 битах получается 37 комбинаций.
2 Есть разновидности кода Грея. В часности, balanced Gray code, который бы идеально подошел для данной задачи. Но как его генерировать компактным кодом не понятно, и по всей видимости, задача совсем не простая. В случае с 8-ми битным счетчиком все просто - можно было бы брать значения из заранее составленой таблицы, а вот как быть с 16 и 32 разрядными счетчиками? Может быть кто-то реализовывал?
1 Код Джонсона не подошел: он слишком избыточный. На 8 битах получается 37 комбинаций.
2 Есть разновидности кода Грея. В часности, balanced Gray code, который бы идеально подошел для данной задачи. Но как его генерировать компактным кодом не понятно, и по всей видимости, задача совсем не простая. В случае с 8-ми битным счетчиком все просто - можно было бы брать значения из заранее составленой таблицы, а вот как быть с 16 и 32 разрядными счетчиками? Может быть кто-то реализовывал?
Из Википедии:
Цитата
Алгоритм преобразования из двоичной системы счисления в код Грея, записанный на языке 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;
}
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;
}
Цитата(Herz @ Nov 4 2008, 20:19)
Из Википедии:
Это стандартный код Грея. Нужен сбалансированный код Грея.
Цитата(vazhko @ Nov 4 2008, 19:30)
Это стандартный код Грея. Нужен сбалансированный код Грея.
Честно говоря, не знаю их отличий. Насколько он эффективнее стандартного в рассматриваемом смысле? Может, выигрыш не столь значителен, чтобы усложнять реализацию?
патент в помощь
Цитата(Herz @ Nov 4 2008, 23:00)
Честно говоря, не знаю их отличий. Насколько он эффективнее стандартного в рассматриваемом смысле? Может, выигрыш не столь значителен, чтобы усложнять реализацию?
Действительно, выигрыш получается небольшой (в 2 раза потив стандартного), но все же... Мне кажется, что как все гениальное, реализация алгоритма может оказаться простой.
Цитата(НЕХ @ Nov 4 2008, 23:05)
патент в помощь
Вот за это огромное спасибо! Буду
всё и в правду, покажется просто, если поймёшь код Бина
только в этом патенте ругают и этот алгоритм...
а вот приветы от атмел, интел и микрософт.
курите на здоровье !
только результаты на общее обсуждение !
а вот приветы от атмел, интел и микрософт.
курите на здоровье !
только результаты на общее обсуждение !
Цитата(НЕХ @ Nov 5 2008, 02:27)
только в этом патенте ругают и этот алгоритм...
а вот приветы от атмел, интел и микрософт.
курите на здоровье !
только результаты на общее обсуждение !
а вот приветы от атмел, интел и микрософт.
курите на здоровье !
только результаты на общее обсуждение !
Еще раз спасибо. Отпишусь обязательно, только закончу предыдущий проект.
не копая глубоко, имею вопросы...
на ресурс памяти что оказывает большее негативное действие :
стирание или запись "0"?
при стирании подвергаются ли износу биты = "1" ?
всегда ли предшествует записи операция стирания ?
стирание едино для байта или индивидуально для каждого бита, в зависимости от его состояния ?
имеет ли смысл использовать вместо битов целиком байты ?( прописывать 00h или FFh, а при анализе сравнивать кол-во 0 и 1 в байте и принимать решение по большинству)
ущербная ячейка куда будет склонять - к 0 или 1 ?
на ресурс памяти что оказывает большее негативное действие :
стирание или запись "0"?
при стирании подвергаются ли износу биты = "1" ?
всегда ли предшествует записи операция стирания ?
стирание едино для байта или индивидуально для каждого бита, в зависимости от его состояния ?
имеет ли смысл использовать вместо битов целиком байты ?( прописывать 00h или FFh, а при анализе сравнивать кол-во 0 и 1 в байте и принимать решение по большинству)
ущербная ячейка куда будет склонять - к 0 или 1 ?
Цитата(НЕХ @ Nov 5 2008, 14:56)
имеет ли смысл использовать вместо битов целиком байты ?( прописывать 00h или FFh, а при анализе сравнивать кол-во 0 и 1 в байте и принимать решение по большинству)
ущербная ячейка куда будет склонять - к 0 или 1 ?
ущербная ячейка куда будет склонять - к 0 или 1 ?
Совершенно верно. Так и планирую сделать. Не вдаваясь в подробности функционирования EEPROM конкретного взятого контроллера. Обращение (запись/чтение/ стирание) к ячейке EEPROM происходит побайтно. Стирание перед записью обязательно. Какие операции оказывают негативное воздействие не знаю. Надо читать теорию.
а попадались ли рекомендации непосредственно производителей контроллеров на эту тему ?
Цитата(НЕХ @ Nov 5 2008, 15:45)
а попадались ли рекомендации непосредственно производителей контроллеров на эту тему ?
Не попадались, по крайней мере у Микрочипа.
Цитата(vazhko @ Oct 29 2008, 16:30)
Прошу помощи в следующей задаче.
Имеем массив энергонезависимой памяти (EEPROM) с ограниченным количеством перезаписи битов(число перезаписей около 1Е6).
Надо каждый раз писать в эту память значения счетчика при его инкременте. Допустим счетчик 32-битный. При инкременте на единицу, младший бит регистра изменяется настолько часто, что можно получить его неработоспособность всего регистра еще до того, как он заполнится. Соответственно, старший бит измениться всего один раз. Существует ли алгоритм такого представления числа(прямой и обратный, на подобие кода Грея), чтобы при последовательном инкременте до заполнения регистра, количество модификаций битов в регистре была примерно равна и минимальна. Разрядность преставления может быть больше разрядности самого числа.
Имеем массив энергонезависимой памяти (EEPROM) с ограниченным количеством перезаписи битов(число перезаписей около 1Е6).
Надо каждый раз писать в эту память значения счетчика при его инкременте. Допустим счетчик 32-битный. При инкременте на единицу, младший бит регистра изменяется настолько часто, что можно получить его неработоспособность всего регистра еще до того, как он заполнится. Соответственно, старший бит измениться всего один раз. Существует ли алгоритм такого представления числа(прямой и обратный, на подобие кода Грея), чтобы при последовательном инкременте до заполнения регистра, количество модификаций битов в регистре была примерно равна и минимальна. Разрядность преставления может быть больше разрядности самого числа.
У вас в вопросе уже готовый ответ, как биты не переставляй а гарантированный срок службы EEPROM 1-миллион циклов записей. Вам надо определится как часто будет запись, а то
Цитата
изменяется настолько часто что можно получить его неработоспособность
это не цифры, например 1 раз в секунду, или сколько ?
если речь идет о количествах циклов записи более 10 тысяч в год, то для таких целей вероятно следует использовать другой тип памяти - энергонезависимое ОЗУ, например ibutton, срок службы ~10 лет,если мало то по прошествии срока, стоит обновить девайс :-)
Цитата(atlantic @ Nov 5 2008, 18:32)
У вас в вопросе уже готовый ответ, как биты не переставляй а гарантированный срок службы EEPROM 1-миллион циклов записей.
Не всего EEPROM, а стираний/записей в конкретный регистр. Причем под 1 бит, будет отводится 1 байт.
Цитата(atlantic @ Nov 5 2008, 18:32)
Цитата
изменяется настолько часто что можно получить его неработоспособность
это не цифры, например 1 раз в секунду, или сколько ?
Речь идет об относительной частоте. При заполнении счетчика в обычном представлении или в стандартном коде Грея, биты переключаются разное количество раз, а младший чаще всех. Задача выравнять количество переключений бит, но чтобы отличие соседних чисел в счетчике было только в одном разряде.
Цитата(atlantic @ Nov 5 2008, 18:32)
если речь идет о количествах циклов записи более 10 тысяч в год, то для таких целей вероятно следует использовать другой тип памяти - энергонезависимое ОЗУ, например ibutton, срок службы ~10 лет,если мало то по прошествии срока, стоит обновить девайс :-)
Есть разные хардварные решения данной задачи и попроще, чем применение энергонезависимого ОЗУ. Но, в данном конкретном случае, интересна именно программная реализация, т.к. задача не с нуля - железо УЖЕ есть.
Цитата(НЕХ @ Nov 5 2008, 13:56)
не копая глубоко, имею вопросы...
на ресурс памяти что оказывает большее негативное действие :
стирание или запись "0"?
при стирании подвергаются ли износу биты = "1" ?
всегда ли предшествует записи операция стирания ?
стирание едино для байта или индивидуально для каждого бита, в зависимости от его состояния ?
имеет ли смысл использовать вместо битов целиком байты ?( прописывать 00h или FFh, а при анализе сравнивать кол-во 0 и 1 в байте и принимать решение по большинству)
ущербная ячейка куда будет склонять - к 0 или 1 ?
на ресурс памяти что оказывает большее негативное действие :
стирание или запись "0"?
при стирании подвергаются ли износу биты = "1" ?
всегда ли предшествует записи операция стирания ?
стирание едино для байта или индивидуально для каждого бита, в зависимости от его состояния ?
имеет ли смысл использовать вместо битов целиком байты ?( прописывать 00h или FFh, а при анализе сравнивать кол-во 0 и 1 в байте и принимать решение по большинству)
ущербная ячейка куда будет склонять - к 0 или 1 ?
Для Flash памяти стирание приводит к установке в 1. Запись осуществляет установку в 0.
Для ресурса имеет значение количество стираний.
Для EEPROM производится запись и поэтому разницы нет. Для ресурса имеет значение изменение состояния.
МСМ.
Цитата(vazhko @ Nov 5 2008, 20:44)
Не всего EEPROM, а стираний/записей в конкретный регистр. Причем под 1 бит, будет отводится 1 байт.
это не цифры, например 1 раз в секунду, или сколько ?
Речь идет об относительной частоте. При заполнении счетчика в обычном представлении или в стандартном коде Грея, биты переключаются разное количество раз, а младший чаще всех. Задача выравнять количество переключений бит, но чтобы отличие соседних чисел в счетчике было только в одном разряде.
Есть разные хардварные решения данной задачи и попроще, чем применение энергонезависимого ОЗУ. Но, в данном конкретном случае, интересна именно программная реализация, т.к. задача не с нуля - железо УЖЕ есть.
это не цифры, например 1 раз в секунду, или сколько ?
Речь идет об относительной частоте. При заполнении счетчика в обычном представлении или в стандартном коде Грея, биты переключаются разное количество раз, а младший чаще всех. Задача выравнять количество переключений бит, но чтобы отличие соседних чисел в счетчике было только в одном разряде.
Есть разные хардварные решения данной задачи и попроще, чем применение энергонезависимого ОЗУ. Но, в данном конкретном случае, интересна именно программная реализация, т.к. задача не с нуля - железо УЖЕ есть.
И всетаки, какой EEPROM и сколько(в абсолютных величинах- разы :) циклов записи в год предполагаете?
Может чего-то я не понимаю ? Есть даташит на девайс, там оговорено максимальное кол-во циклов, причем не очень четко, т.е. для своих целей надо брать с запасом. Как бы биты не переставлялись, а операции записи от этого не уменьшатся(в кол-ве раз) так ведь, или я что то не понял? Как внутри работает EEPROM четко не специфицируется, и расчитывать на то, что при записи одинаковых значений несколько раз подряд, будь то хоть 0 хоть FF, общее кол-во допустимых(при которых нет отказов) циклов записи уменьшится нет никаких оснований. Есть физические процессы которые влияют на отказы при записи, и они зависят от температуры окружающей среды, напряжений питаний, технологии по которой изготовлена EEPROM. В даташите приведен усредненный параметр работы без отказов. Самый надежный способ работать без отказов - это придерживаться параметров даташит с запасом.
Цитата(atlantic @ Nov 6 2008, 12:32)
Может чего-то я не понимаю ? Есть даташит на девайс, там оговорено максимальное кол-во циклов, причем не очень четко, т.е. для своих целей надо брать с запасом. Как бы биты не переставлялись, а операции записи от этого не уменьшатся(в кол-ве раз) так ведь, или я что то не понял? Как внутри работает EEPROM четко не специфицируется, и расчитывать на то, что при записи одинаковых значений несколько раз подряд, будь то хоть 0 хоть FF, общее кол-во допустимых(при которых нет отказов) циклов записи уменьшится нет никаких оснований.
Дык, в том и прикол, что перезаписываюся только изменившиеся биты. И только один (в идеале) за инкремент. Нет смысла перезаписывать ту позицию, которую не надо менять.
Цитата(vazhko @ Nov 5 2008, 19:44)
Речь идет об относительной частоте. При заполнении счетчика в обычном представлении или в стандартном коде Грея, биты переключаются разное количество раз, а младший чаще всех. Задача выравнять количество переключений бит, но чтобы отличие соседних чисел в счетчике было только в одном разряде.
Похоже, не так-то просто придумать алгоритм, дающий сбалансированный код Грея: в литературе в основном ограничиваются доказательствами, что такие коды существуют.
А наверное енто всё так просто не просчитать.. 
Как я понял в ПЗУ организуется просто последовательный счётчик
Если места в EEPROMe много, что можно под бит использовать байт, то можно поступить и проще:
писать "прямым" и удобным для использования двоичным кодом и байт пряма в свой байт, но просто переносить весь (или начиная с младших байтов) в другие ячейки, а ячейки с выработанным ресурсов просто обходить.
В этом деле можно смотреть на какой-нибудь большой разряд (например 18) и по его сбросу делать перенос всего счётчика (или его части) в другой набор ячеек, отмечая это смещение в специальной ячейке.
вот и всё
Да. Есть подозрение, что часто используемые ячейки не дадут паспортной длительности хранения (а ещё перепады температуры и т.п.).
Как я понял в ПЗУ организуется просто последовательный счётчик
Если места в EEPROMe много, что можно под бит использовать байт, то можно поступить и проще:
писать "прямым" и удобным для использования двоичным кодом и байт пряма в свой байт, но просто переносить весь (или начиная с младших байтов) в другие ячейки, а ячейки с выработанным ресурсов просто обходить.
В этом деле можно смотреть на какой-нибудь большой разряд (например 18) и по его сбросу делать перенос всего счётчика (или его части) в другой набор ячеек, отмечая это смещение в специальной ячейке.
вот и всё
Да. Есть подозрение, что часто используемые ячейки не дадут паспортной длительности хранения (а ещё перепады температуры и т.п.).
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.