реклама на сайте
подробности

 
 
> Равномерный износ битов, Алгоритм представления числа в регистре
vazhko
сообщение Oct 29 2008, 12:30
Сообщение #1


Участник
*

Группа: Участник
Сообщений: 15
Регистрация: 1-02-06
Пользователь №: 13 875



Прошу помощи в следующей задаче.
Имеем массив энергонезависимой памяти (EEPROM) с ограниченным количеством перезаписи битов(число перезаписей около 1Е6).
Надо каждый раз писать в эту память значения счетчика при его инкременте. Допустим счетчик 32-битный. При инкременте на единицу, младший бит регистра изменяется настолько часто, что можно получить его неработоспособность всего регистра еще до того, как он заполнится. Соответственно, старший бит измениться всего один раз. Существует ли алгоритм такого представления числа(прямой и обратный, на подобие кода Грея), чтобы при последовательном инкременте до заполнения регистра, количество модификаций битов в регистре была примерно равна и минимальна. Разрядность преставления может быть больше разрядности самого числа.
Go to the top of the page
 
+Quote Post
2 страниц V   1 2 >  
Start new topic
Ответов (1 - 28)
Polaris
сообщение Oct 29 2008, 12:47
Сообщение #2


Местный
***

Группа: Свой
Сообщений: 266
Регистрация: 8-12-05
Пользователь №: 11 964



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

Код Джонсона?
Go to the top of the page
 
+Quote Post
MrYuran
сообщение Oct 29 2008, 12:48
Сообщение #3


Беспросветный оптимист
******

Группа: Свой
Сообщений: 4 640
Регистрация: 26-12-07
Из: Н.Новгород
Пользователь №: 33 646



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


--------------------
Программирование делится на системное и бессистемное. ©Моё :)
— а для кого-то БГ — это Bill Gilbert =)
Go to the top of the page
 
+Quote Post
vazhko
сообщение Oct 29 2008, 13:19
Сообщение #4


Участник
*

Группа: Участник
Сообщений: 15
Регистрация: 1-02-06
Пользователь №: 13 875



Polaris, MrYuran.
Спасибо большое, по-моему самое оно.
Буду думать о реализации алгоритма.
Go to the top of the page
 
+Quote Post
Herz
сообщение Oct 29 2008, 13:32
Сообщение #5


Гуру
******

Группа: Модераторы
Сообщений: 10 983
Регистрация: 23-11-05
Пользователь №: 11 287



Цитата(MrYuran @ Oct 29 2008, 14:48) *
00000001
00000011
00000111
00001111
00011111
00111111
01111111
11111111
00000010
00000110
00001110
00011110
...


11111111
11111110
11111100
....
?
Go to the top of the page
 
+Quote Post
alexander55
сообщение Oct 29 2008, 13:36
Сообщение #6


Бывалый
*****

Группа: Свой
Сообщений: 1 584
Регистрация: 7-08-07
Пользователь №: 29 615



Цитата(Herz @ Oct 29 2008, 16:32) *
11111111
11111110
11111100
....
?

Да, он так и предложил (инверсно).
Только, уточню
11111111
11111110
11111101
....
Go to the top of the page
 
+Quote Post
Herz
сообщение Oct 29 2008, 16:25
Сообщение #7


Гуру
******

Группа: Модераторы
Сообщений: 10 983
Регистрация: 23-11-05
Пользователь №: 11 287



Цитата(alexander55 @ Oct 29 2008, 15:36) *
Да, он так и предложил (инверсно).
Только, уточню
11111111
11111110
11111101
....

нет, так два бита за раз меняются, а это нехорошо.
Go to the top of the page
 
+Quote Post
scifi
сообщение Oct 29 2008, 16:45
Сообщение #8


Гуру
******

Группа: Свой
Сообщений: 3 020
Регистрация: 7-02-07
Пользователь №: 25 136



Цитата(vazhko @ Oct 29 2008, 15:30) *
Имеем массив энергонезависимой памяти (EEPROM) с ограниченным количеством перезаписи битов(число перезаписей около 1Е6).

А я думал, что у EEPROM считается ресурс байтов, а не битов. То есть при перезаписи байт стирается целиком.
Если так, что нужна такая кодировка счётчика, чтобы при последовательных приращениях все байты счётчика изменялись с равной частотой. Я такую схему реализовывал. Причём описание нашёл в каком-то патенте США. Идея очевидная, но всё равно приятно, когда всё разжёвано. Жаль, не могу отыскать номер того патента...
Go to the top of the page
 
+Quote Post
alexander55
сообщение Oct 30 2008, 09:06
Сообщение #9


Бывалый
*****

Группа: Свой
Сообщений: 1 584
Регистрация: 7-08-07
Пользователь №: 29 615



Цитата(Herz @ Oct 29 2008, 19:25) *
нет, так два бита за раз меняются, а это нехорошо.

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

Цитата(scifi @ Oct 29 2008, 19:45) *
А я думал, что у EEPROM считается ресурс байтов, а не битов. То есть при перезаписи байт стирается целиком.

По физике - это количество перезарядов, которые надо минимизировать.
Go to the top of the page
 
+Quote Post
vazhko
сообщение Nov 4 2008, 14:37
Сообщение #10


Участник
*

Группа: Участник
Сообщений: 15
Регистрация: 1-02-06
Пользователь №: 13 875



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

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

2 Есть разновидности кода Грея. В часности, balanced Gray code, который бы идеально подошел для данной задачи. Но как его генерировать компактным кодом не понятно, и по всей видимости, задача совсем не простая. В случае с 8-ми битным счетчиком все просто - можно было бы брать значения из заранее составленой таблицы, а вот как быть с 16 и 32 разрядными счетчиками? Может быть кто-то реализовывал?
Go to the top of the page
 
+Quote Post
Herz
сообщение Nov 4 2008, 16:19
Сообщение #11


Гуру
******

Группа: Модераторы
Сообщений: 10 983
Регистрация: 23-11-05
Пользователь №: 11 287



Из Википедии:
Цитата
Алгоритм преобразования из двоичной системы счисления в код Грея, записанный на языке 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;

}
Go to the top of the page
 
+Quote Post
vazhko
сообщение Nov 4 2008, 17:30
Сообщение #12


Участник
*

Группа: Участник
Сообщений: 15
Регистрация: 1-02-06
Пользователь №: 13 875



Цитата(Herz @ Nov 4 2008, 20:19) *
Из Википедии:

Это стандартный код Грея. Нужен сбалансированный код Грея.
Go to the top of the page
 
+Quote Post
Herz
сообщение Nov 4 2008, 19:00
Сообщение #13


Гуру
******

Группа: Модераторы
Сообщений: 10 983
Регистрация: 23-11-05
Пользователь №: 11 287



Цитата(vazhko @ Nov 4 2008, 19:30) *
Это стандартный код Грея. Нужен сбалансированный код Грея.

Честно говоря, не знаю их отличий. Насколько он эффективнее стандартного в рассматриваемом смысле? Может, выигрыш не столь значителен, чтобы усложнять реализацию?
Go to the top of the page
 
+Quote Post
НЕХ
сообщение Nov 4 2008, 19:05
Сообщение #14


Профессионал
*****

Группа: Участник
Сообщений: 1 220
Регистрация: 10-10-06
Из: Петербург
Пользователь №: 21 169



патент в помощь
Прикрепленные файлы
Прикрепленный файл  US_6084935.pdf ( 56.06 килобайт ) Кол-во скачиваний: 212
 


--------------------
Когда едешь на поезде - переезд всегда закрыт...
Go to the top of the page
 
+Quote Post
vazhko
сообщение Nov 4 2008, 21:30
Сообщение #15


Участник
*

Группа: Участник
Сообщений: 15
Регистрация: 1-02-06
Пользователь №: 13 875



Цитата(Herz @ Nov 4 2008, 23:00) *
Честно говоря, не знаю их отличий. Насколько он эффективнее стандартного в рассматриваемом смысле? Может, выигрыш не столь значителен, чтобы усложнять реализацию?

Действительно, выигрыш получается небольшой (в 2 раза потив стандартного), но все же... Мне кажется, что как все гениальное, реализация алгоритма может оказаться простой.
Цитата(НЕХ @ Nov 4 2008, 23:05) *
патент в помощь

Вот за это огромное спасибо! Буду курить изучать.
Go to the top of the page
 
+Quote Post
yafalschivii
сообщение Nov 4 2008, 22:09
Сообщение #16





Группа: Новичок
Сообщений: 6
Регистрация: 17-10-08
Из: г. Омск
Пользователь №: 41 021



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


--------------------
Расчёт электромагнитного поля коаксиальной линии передачи
Go to the top of the page
 
+Quote Post
НЕХ
сообщение Nov 4 2008, 22:27
Сообщение #17


Профессионал
*****

Группа: Участник
Сообщений: 1 220
Регистрация: 10-10-06
Из: Петербург
Пользователь №: 21 169



только в этом патенте ругают и этот алгоритм...
а вот приветы от атмел, интел и микрософт.
курите на здоровье !
только результаты на общее обсуждение !
Прикрепленные файлы
Прикрепленный файл  US6792065.pdf ( 129.8 килобайт ) Кол-во скачиваний: 127
Прикрепленный файл  US7065607.pdf ( 129.3 килобайт ) Кол-во скачиваний: 100
Прикрепленный файл  US6249562.pdf ( 172.01 килобайт ) Кол-во скачиваний: 152
 


--------------------
Когда едешь на поезде - переезд всегда закрыт...
Go to the top of the page
 
+Quote Post
vazhko
сообщение Nov 5 2008, 10:33
Сообщение #18


Участник
*

Группа: Участник
Сообщений: 15
Регистрация: 1-02-06
Пользователь №: 13 875



Цитата(НЕХ @ Nov 5 2008, 02:27) *
только в этом патенте ругают и этот алгоритм...
а вот приветы от атмел, интел и микрософт.
курите на здоровье !
только результаты на общее обсуждение !

Еще раз спасибо. Отпишусь обязательно, только закончу предыдущий проект.
Go to the top of the page
 
+Quote Post
НЕХ
сообщение Nov 5 2008, 10:56
Сообщение #19


Профессионал
*****

Группа: Участник
Сообщений: 1 220
Регистрация: 10-10-06
Из: Петербург
Пользователь №: 21 169



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


--------------------
Когда едешь на поезде - переезд всегда закрыт...
Go to the top of the page
 
+Quote Post
vazhko
сообщение Nov 5 2008, 11:31
Сообщение #20


Участник
*

Группа: Участник
Сообщений: 15
Регистрация: 1-02-06
Пользователь №: 13 875



Цитата(НЕХ @ Nov 5 2008, 14:56) *
имеет ли смысл использовать вместо битов целиком байты ?( прописывать 00h или FFh, а при анализе сравнивать кол-во 0 и 1 в байте и принимать решение по большинству)
ущербная ячейка куда будет склонять - к 0 или 1 ?

Совершенно верно. Так и планирую сделать. Не вдаваясь в подробности функционирования EEPROM конкретного взятого контроллера. Обращение (запись/чтение/ стирание) к ячейке EEPROM происходит побайтно. Стирание перед записью обязательно. Какие операции оказывают негативное воздействие не знаю. Надо читать теорию.
Go to the top of the page
 
+Quote Post
НЕХ
сообщение Nov 5 2008, 11:45
Сообщение #21


Профессионал
*****

Группа: Участник
Сообщений: 1 220
Регистрация: 10-10-06
Из: Петербург
Пользователь №: 21 169



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


--------------------
Когда едешь на поезде - переезд всегда закрыт...
Go to the top of the page
 
+Quote Post
vazhko
сообщение Nov 5 2008, 12:07
Сообщение #22


Участник
*

Группа: Участник
Сообщений: 15
Регистрация: 1-02-06
Пользователь №: 13 875



Цитата(НЕХ @ Nov 5 2008, 15:45) *
а попадались ли рекомендации непосредственно производителей контроллеров на эту тему ?

Не попадались, по крайней мере у Микрочипа.
Go to the top of the page
 
+Quote Post
atlantic
сообщение Nov 5 2008, 14:32
Сообщение #23


участник
****

Группа: Свой
Сообщений: 573
Регистрация: 16-02-06
Пользователь №: 14 402



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

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

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

если речь идет о количествах циклов записи более 10 тысяч в год, то для таких целей вероятно следует использовать другой тип памяти - энергонезависимое ОЗУ, например ibutton, срок службы ~10 лет,если мало то по прошествии срока, стоит обновить девайс :-)
Go to the top of the page
 
+Quote Post
vazhko
сообщение Nov 5 2008, 16:44
Сообщение #24


Участник
*

Группа: Участник
Сообщений: 15
Регистрация: 1-02-06
Пользователь №: 13 875



Цитата(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 лет,если мало то по прошествии срока, стоит обновить девайс :-)

Есть разные хардварные решения данной задачи и попроще, чем применение энергонезависимого ОЗУ. Но, в данном конкретном случае, интересна именно программная реализация, т.к. задача не с нуля - железо УЖЕ есть.
Go to the top of the page
 
+Quote Post
alexander55
сообщение Nov 6 2008, 08:14
Сообщение #25


Бывалый
*****

Группа: Свой
Сообщений: 1 584
Регистрация: 7-08-07
Пользователь №: 29 615



Цитата(НЕХ @ Nov 5 2008, 13:56) *
не копая глубоко, имею вопросы...
на ресурс памяти что оказывает большее негативное действие :
стирание или запись "0"?
при стирании подвергаются ли износу биты = "1" ?
всегда ли предшествует записи операция стирания ?
стирание едино для байта или индивидуально для каждого бита, в зависимости от его состояния ?
имеет ли смысл использовать вместо битов целиком байты ?( прописывать 00h или FFh, а при анализе сравнивать кол-во 0 и 1 в байте и принимать решение по большинству)
ущербная ячейка куда будет склонять - к 0 или 1 ?

Для Flash памяти стирание приводит к установке в 1. Запись осуществляет установку в 0.
Для ресурса имеет значение количество стираний.
Для EEPROM производится запись и поэтому разницы нет. Для ресурса имеет значение изменение состояния.
МСМ.
Go to the top of the page
 
+Quote Post
atlantic
сообщение Nov 6 2008, 08:32
Сообщение #26


участник
****

Группа: Свой
Сообщений: 573
Регистрация: 16-02-06
Пользователь №: 14 402



Цитата(vazhko @ Nov 5 2008, 20:44) *
Не всего EEPROM, а стираний/записей в конкретный регистр. Причем под 1 бит, будет отводится 1 байт.

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

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

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

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

Может чего-то я не понимаю ? Есть даташит на девайс, там оговорено максимальное кол-во циклов, причем не очень четко, т.е. для своих целей надо брать с запасом. Как бы биты не переставлялись, а операции записи от этого не уменьшатся(в кол-ве раз) так ведь, или я что то не понял? Как внутри работает EEPROM четко не специфицируется, и расчитывать на то, что при записи одинаковых значений несколько раз подряд, будь то хоть 0 хоть FF, общее кол-во допустимых(при которых нет отказов) циклов записи уменьшится нет никаких оснований. Есть физические процессы которые влияют на отказы при записи, и они зависят от температуры окружающей среды, напряжений питаний, технологии по которой изготовлена EEPROM. В даташите приведен усредненный параметр работы без отказов. Самый надежный способ работать без отказов - это придерживаться параметров даташит с запасом.
Go to the top of the page
 
+Quote Post
vazhko
сообщение Nov 6 2008, 10:06
Сообщение #27


Участник
*

Группа: Участник
Сообщений: 15
Регистрация: 1-02-06
Пользователь №: 13 875



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

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

Сообщение отредактировал vazhko - Nov 6 2008, 10:08
Go to the top of the page
 
+Quote Post
scifi
сообщение Nov 6 2008, 12:11
Сообщение #28


Гуру
******

Группа: Свой
Сообщений: 3 020
Регистрация: 7-02-07
Пользователь №: 25 136



Цитата(vazhko @ Nov 5 2008, 19:44) *
Речь идет об относительной частоте. При заполнении счетчика в обычном представлении или в стандартном коде Грея, биты переключаются разное количество раз, а младший чаще всех. Задача выравнять количество переключений бит, но чтобы отличие соседних чисел в счетчике было только в одном разряде.

Похоже, не так-то просто придумать алгоритм, дающий сбалансированный код Грея: в литературе в основном ограничиваются доказательствами, что такие коды существуют.
Go to the top of the page
 
+Quote Post
GoG
сообщение Nov 10 2008, 22:31
Сообщение #29





Группа: Новичок
Сообщений: 2
Регистрация: 16-05-06
Пользователь №: 17 132



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

Да. Есть подозрение, что часто используемые ячейки не дадут паспортной длительности хранения (а ещё перепады температуры и т.п.).
Go to the top of the page
 
+Quote Post

2 страниц V   1 2 >
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 22nd July 2025 - 00:03
Рейтинг@Mail.ru


Страница сгенерированна за 0.01686 секунд с 7
ELECTRONIX ©2004-2016