IPB

Welcome Guest ( Log In | Register )

3 Pages V  < 1 2 3 >  
Reply to this topicStart new topic
Triangular Probability Density Function Dither, How does this random number exaclty work
Jasper
post Jan 9 2004, 13:06
Post #26





Group: Members
Posts: 189
Joined: 9-July 02
Member No.: 2536



Actually I think you'd want something symmetrical, so as not to create a DC bias, which is done perfectly when adding two independent rectangular generators with the same range.
As for the number of bits used, a few posts earlier someone said that a range of 1 bit (peak-to-peak?) would be enough for triangular dither, but I have also heard of 2 bits being best (Principles of Digital Audio, Ken C. Pohlmann, and this also seems to be what 2Bdecided is suggesting). Perhaps someone can clear this up.
Go to the top of the page
+Quote Post
2Bdecided
post Jan 9 2004, 13:29
Post #27


ReplayGain developer


Group: Developer
Posts: 5250
Joined: 5-November 01
From: Yorkshire, UK
Member No.: 409



QUOTE (Ariakis @ Jan 9 2004, 08:04 AM)
Just a note on what David said about a triangular generator being a combination of two rectangular generators...

He said that to get 8 bits of triangualr pseudorands, you'd need to combine two rectangular generators with ranges of [0, 255].  This, however, would allow a total range of [0, 510], which is more than 8 bits.

So to get 8 bits of triangular dither, you'd need to combine [0, 127] and [0, 128] rectangular generators to get a [0, 255] triangular generator.  At least, I think.

So, in your case, you'd want 3 bits of noise, which is [0, 7]... so you'd want to combine [0, 3] and [0, 4] rectangular generators, I think.

Someone correct me if I'm wrong, please. =)

Triangular dither must be two bits peak to peak, so I'm affraid you're not right!

Correct triangular dither removes noise modulation - that means that the resulting noise (after truncation) from adding dither will be independent of the level of the original signal.

Rectangular dither doesn't so this properly. If the original signal lies exactly half way between two steps in the least significant bit of the truncated signal, then it can be bumped up or down by 0.5 bits - therefore the resulting noise (noise=final-original) will always have a magnitude of 0.5 bits. Whereas if the original signal is elsewhere, the magnitude of the noise (i.e. the rounding error) will be different, and signal dependent.

Triangular dither solves this by always giving the rounded signal the chance of being the same number of "bits" (or fractions of one bit) away from its original value. Without scanning a picture in, I can't explain this any better.

If you only have 1 bit peak to peak triangular dither (that's called 0.5 bits in Cool Edit for some reason), then it will cause even worse noise modulation than recntangular dither, and won't even remove harmonic distortion.

So it must always be 2 bits peak to peak.

Cheers,
David.
(That's "Dr David Robinson" for your credits aristotel! I nearly did an MSc at York, and I've stayed there a time or two (once at the uni) - I won't hold you to that drink though! - I'm a long way away now.)
Go to the top of the page
+Quote Post
goli
post May 29 2005, 19:02
Post #28





Group: Members
Posts: 1
Joined: 29-May 05
Member No.: 22382



Hi everybody, I just visited this page and i was wondering if anybody can help me with a question about dithering.
I want to reduce the # of bits from 8 to 4 and i want to use rectangular dither . So, i have to add a 4-bit random signal to the original one before quantizing. I just don't know what to do with boundries . For example , if the original value is 255 evey positive dither will make the total value to have 9 bits and i am not sure what to do with it.

Thanks in advance,
Go to the top of the page
+Quote Post
spoon
post Jun 15 2005, 10:11
Post #29


dBpowerAMP developer


Group: Developer (Donating)
Posts: 2755
Joined: 24-March 02
Member No.: 1615



To quote shibatch "Dithered 8bit files contains strong supersonic, and listening to these files for long hours may damage your hearing. Dithered 16bit files are no
problem since the power of the supersonic of dither is 1/65536 of those of
dithered 8bit files."

4 bit would be even worse...


--------------------
Spoon http://www.dbpoweramp.com
Go to the top of the page
+Quote Post
KikeG
post Jun 15 2005, 13:13
Post #30


WinABX developer


Group: Developer
Posts: 1578
Joined: 1-October 01
Member No.: 137



That depends largely on the sample rate.
Go to the top of the page
+Quote Post
2Bdecided
post Jun 16 2005, 11:37
Post #31


ReplayGain developer


Group: Developer
Posts: 5250
Joined: 5-November 01
From: Yorkshire, UK
Member No.: 409



QUOTE (goli @ May 29 2005, 06:02 PM)
Hi everybody,  I just visited this page and i was wondering if anybody can help me with a question about dithering. 
I want to reduce the # of bits from 8 to 4 and i want to use rectangular dither . So, i have to add a 4-bit random signal to the original one before quantizing.  I just  don't know what to do with boundries . For example , if the original value is 255 evey positive dither will make the total value to have 9 bits  and i am not sure what to do with it.
*


Clip it - if you already have a full scale sample, then dither can send this 1 bit (or 2 bit, with triangular dither) over full scale. Check for it in the code, and ensure values over 255 are clipped to 255. Also ensure you don't go below 0.

If you're not careful, you'll overflow 255 to 0 or 0 to 255, and that will sound terrible!

4-bit audio will sound terrible anyway - what project are you working on? Is it interesting, or experimental?

Cheers,
David.
Go to the top of the page
+Quote Post
Nika
post Jun 16 2005, 14:50
Post #32





Group: Members
Posts: 24
Joined: 14-April 05
Member No.: 21432



Sorry, guys, I've only just seen the thread and haven't read all the way through it. The bit depth of the dither is not "2 bits" but rather "2 quantization steps" (of the remaining quanta). 2 bits implies the options of 00, 01, 10, and 11. 2 quanta implies 00, 01 and 10. The dither must be of triangular probability within this range. The way to generate the dither is to generate one bit's worth of random values twice, so:

Random value between 0000 (bits 13 through 16) and 0100. Do this twice and add them together.

You now have TPDF dither of 2 quanta in amplitude (not 2 bits). The result will be some value between 0000 and 1000 with the greatest likelihood that the number will be 0100.

To the person that asked, this is precisely the amount and type of dither needed in order to completely remove quantization distortion (or rather turn it into noise). This has been mathematically proven and you can find these proofs in the writings of Lipshitz and Vanderkooy.

I hope this helps?

Nika
Go to the top of the page
+Quote Post
Nika
post Jun 16 2005, 14:55
Post #33





Group: Members
Posts: 24
Joined: 14-April 05
Member No.: 21432



QUOTE (goli @ May 29 2005, 12:02 PM)
Hi everybody,  I just visited this page and i was wondering if anybody can help me with a question about dithering. 
I want to reduce the # of bits from 8 to 4 and i want to use rectangular dither . So, i have to add a 4-bit random signal to the original one before quantizing.  I just  don't know what to do with boundries . For example , if the original value is 255 evey positive dither will make the total value to have 9 bits  and i am not sure what to do with it.

Thanks in advance,
*


First, don't use rectangular dither. Second, dither is a signal added to the original. If you have no headroom you will assuredly clip when adding this signal. Either gain adjust the original ahead of time or acknowledge that you are going to clip. Third, if this is really audio you may want to try noiseshaping instead of dithering if you're going to 4 bits. That's a very low dynamic range and you can steal some additional dynamic range by noiseshaping it appropriately.

Nika
Go to the top of the page
+Quote Post
madshi
post Aug 27 2007, 15:47
Post #34





Group: Members
Posts: 16
Joined: 27-August 07
Member No.: 46548



QUOTE (Nika @ Jun 16 2005, 14:50) *
Sorry, guys, I've only just seen the thread and haven't read all the way through it. The bit depth of the dither is not "2 bits" but rather "2 quantization steps" (of the remaining quanta). 2 bits implies the options of 00, 01, 10, and 11. 2 quanta implies 00, 01 and 10. The dither must be of triangular probability within this range. The way to generate the dither is to generate one bit's worth of random values twice, so:

Random value between 0000 (bits 13 through 16) and 0100. Do this twice and add them together.

You now have TPDF dither of 2 quanta in amplitude (not 2 bits). The result will be some value between 0000 and 1000 with the greatest likelihood that the number will be 0100.

To the person that asked, this is precisely the amount and type of dither needed in order to completely remove quantization distortion (or rather turn it into noise). This has been mathematically proven and you can find these proofs in the writings of Lipshitz and Vanderkooy.

Sorry for bringing up an old thread. I'm trying to reduce a signed 24bit PCM track to 20bit. As far as I understand this is what I have to do:

(1) Add a random value of the range [-32..+32].
(2) Add another random value of the range [-32..+32].
(3) Round the resulting PCM sample to 20bit.

Is that correct? Thanks much!!
Go to the top of the page
+Quote Post
Nick.C
post Aug 27 2007, 17:01
Post #35


lossyWAV Developer


Group: Developer
Posts: 1807
Joined: 11-April 07
From: Wherever here is
Member No.: 42400



Is it not simply:

new_value = round(old_value/(2^4)+random-random)

?

This post has been edited by Nick.C: Aug 27 2007, 17:01


--------------------
lossyWAV -q X -a 4 --feedback 4| FLAC -8 ~= 320kbps
Go to the top of the page
+Quote Post
SebastianG
post Aug 27 2007, 17:53
Post #36





Group: Developer
Posts: 1318
Joined: 20-March 04
From: Göttingen (DE)
Member No.: 12875



QUOTE (madshi @ Aug 27 2007, 16:47) *
Sorry for bringing up an old thread. I'm trying to reduce a signed 24bit PCM track to 20bit. As far as I understand this is what I have to do:

(1) Add a random value of the range [-32..+32].
(2) Add another random value of the range [-32..+32].
(3) Round the resulting PCM sample to 20bit.

Is that correct? Thanks much!!


That's too much dither (12 dB more than necessary).

It's as simple as Nick.C pointed out:
new_int20 = round( old_int24 / 16.0 + rnd() - rnd() );
where rnd() returns independently and idendically-distributed values between 0.0 and 1.0

A full TPF dither signal only carries samples values between -d...d where d is the quantizer step size.

A full rectangular dither would be:
new_int20 = round( old_int24 / 16.0 + rnd() - 0.5 );

You can even morph between both distributions:
new_int20 = round( old_int24 / 16.0 + rnd() - 0.5*rnd() - 0.25 );

The choice is really a trade-off between dither noise power and the degree of noise modulation you are willing to accept. For example I prefer the last variant which is as safe as rectangular dither and usually enough to avoid noise modulation -- especially when coupled with noise shaping filters.

Cheers!
SG

This post has been edited by SebastianG: Aug 27 2007, 18:02
Go to the top of the page
+Quote Post
madshi
post Aug 28 2007, 08:23
Post #37





Group: Members
Posts: 16
Joined: 27-August 07
Member No.: 46548



QUOTE (SebastianG @ Aug 27 2007, 17:53) *
That's too much dither (12 dB more than necessary).

It's as simple as Nick.C pointed out:
new_int20 = round( old_int24 / 16.0 + rnd() - rnd() );
where rnd() returns independently and idendically-distributed values between 0.0 and 1.0

I'm trying to avoid floating point math to speed things up. So is this correct for doing TPF?

(1) add a random value of [0..16]
(2) substract a random value of [0..16]
(3) round down to 20bit

I could do it this way without using floating point math.

Thanks much!

P.S: Osterode grüßt Göttingen!! smile.gif
Go to the top of the page
+Quote Post
Nick.C
post Aug 28 2007, 08:31
Post #38


lossyWAV Developer


Group: Developer
Posts: 1807
Joined: 11-April 07
From: Wherever here is
Member No.: 42400



Surely, to round you will have to use FP maths? ...or maybe not....

Pascal:

new_value:=(old_value + random(16) - random(16));

if (new_value and 15)>7 then
new_value:= new_value shr 4 + 1
else
new_value:= new_value shr 4;

This post has been edited by Nick.C: Aug 28 2007, 08:31


--------------------
lossyWAV -q X -a 4 --feedback 4| FLAC -8 ~= 320kbps
Go to the top of the page
+Quote Post
madshi
post Aug 28 2007, 09:02
Post #39





Group: Members
Posts: 16
Joined: 27-August 07
Member No.: 46548



QUOTE (Nick.C @ Aug 28 2007, 08:31) *
Surely, to round you will have to use FP maths? ...or maybe not....

Pascal:

new_value:=(old_value + random(16) - random(16));

if (new_value and 15)>7 then
new_value:= new_value shr 4 + 1
else
new_value:= new_value shr 4;

Heh, yes, I was planning something like that. I still need to check if that works correctly for negative samples, too. Furthermore I still need to add checks for overflow/clipping.

Anyway, the dither/random range is correct now? According to this pdf:

http://www.users.qwest.net/%7Evolt42/caden...erExplained.pdf

... it should be random(17) instead of random(16), or am I wrong?
Go to the top of the page
+Quote Post
SebastianG
post Aug 28 2007, 09:13
Post #40





Group: Developer
Posts: 1318
Joined: 20-March 04
From: Göttingen (DE)
Member No.: 12875



QUOTE (madshi @ Aug 28 2007, 09:23) *
(1) add a random value of [0..16]
(2) substract a random value of [0..16]
(3) round down to 20bit

Then you won't get an exact triangular distribution -- only an approximation.
But it'll be okay in your case, I guess. You could however improve it by doing:
new_sample20 = ( (old_sample24 << 4) + rand(256) - rand(256) + 128 ) >> 8;
where rand(int x) returns equally distributed values from 0 (inclusive) to x (exclusive)
and (>>) is a sign-extending right shift.

QUOTE
P.S: Osterode grüßt Göttingen!! smile.gif

Yay! wink.gif

Cheers!
SG

QUOTE (Nick.C @ Aug 28 2007, 09:31) *
new_value:= new_value shr 4

You have to be careful with the operator 'shr' in Pascal. 'shr' is an extension of the Borland compiler which fills the upper bits always with zeros (no sign-extension).

Cheers!
SG

This post has been edited by SebastianG: Aug 28 2007, 09:08
Go to the top of the page
+Quote Post
madshi
post Aug 28 2007, 09:23
Post #41





Group: Members
Posts: 16
Joined: 27-August 07
Member No.: 46548



QUOTE (SebastianG @ Aug 28 2007, 09:13) *
Then you won't get an exact triangular distribution -- only an approximation.

Why is that?

And shouldn't it be rand(257)?

Thanks much!
Go to the top of the page
+Quote Post
SebastianG
post Aug 28 2007, 14:10
Post #42





Group: Developer
Posts: 1318
Joined: 20-March 04
From: Göttingen (DE)
Member No.: 12875



QUOTE (madshi @ Aug 28 2007, 10:23) *
QUOTE (SebastianG @ Aug 28 2007, 09:13) *
Then you won't get an exact triangular distribution -- only an approximation.

Why is that?

Because you add already discrete quantized values. You end up with a discrete probability distribution = finite amount of possible dither sample values.

QUOTE (madshi @ Aug 28 2007, 10:23) *
And shouldn't it be rand(257)?

No, it was supposed to be 256. This'll lead to the best approximation to the TPDF.
Sketch of proof:
The best approximation of a rectangular PDF for values 0..256 can be done via rand(256)+0.5. This should be obvious. If we substitute the RNG in the formular for a TPDF dither we get:
CODE
new_value20 = ( old_value24 << 4 + (rand(256)+0.5) - (rand(256)+0.5) + 128) >> 8;
            = ( old_value24 << 4 +  rand(256)      -  rand(256)      + 128) >> 8;

Note: (x+128) >> 8  is equivalent to  round(x/256.0)

The 0.5 and -0.5 cancel each other.


Cheers!
SG

This post has been edited by SebastianG: Aug 28 2007, 14:10
Go to the top of the page
+Quote Post
2Bdecided
post Aug 28 2007, 14:18
Post #43


ReplayGain developer


Group: Developer
Posts: 5250
Joined: 5-November 01
From: Yorkshire, UK
Member No.: 409



It's probably worth mentioning a simple trick that's widely used.

Don't generate two random numbers per sample, and subtract them.

Instead, generate one random number per sample, and subtract the previous random number.

So

output = round(scale * input + this_random_number - previous_random_number)

This is still perfectly valid TPF dither, but has the effect of high pass filtering the dither, which is generally a desirable thing for audio (and many other applications).

Cheers,
David.
Go to the top of the page
+Quote Post
Nick.C
post Aug 28 2007, 14:33
Post #44


lossyWAV Developer


Group: Developer
Posts: 1807
Joined: 11-April 07
From: Wherever here is
Member No.: 42400



QUOTE (2Bdecided @ Aug 28 2007, 14:18) *
Don't generate two random numbers per sample, and subtract them.
Instead, generate one random number per sample, and subtract the previous random number.
Sneaky, damned sneaky wink.gif


--------------------
lossyWAV -q X -a 4 --feedback 4| FLAC -8 ~= 320kbps
Go to the top of the page
+Quote Post
madshi
post Aug 28 2007, 14:50
Post #45





Group: Members
Posts: 16
Joined: 27-August 07
Member No.: 46548



QUOTE (SebastianG @ Aug 28 2007, 14:10) *
Because you add already discrete quantized values. You end up with a discrete probability distribution = finite amount of possible dither sample values.

Ok, I think I understand, thank you. One final question: If I use your idea to use "value24 << 4" I've no room left in 32bit processing for detecting overflow, or am I wrong? What do you think about this?

new_sample20 = ( (old_sample24 << 3) + rand(128) - rand(128) + 64 ) >> 7;

This way I'd leave one bit space for potential overflows. What do you think?

P.S: The problem you have with my rand(16) is that the random range is too small, right? Wouldn't it be mathematically equivalent to do this?

new_sample20 = ( old_sample24 + ((rand(256) - rand(256)) >> 4) + 8 ) >> 4;

QUOTE
probably worth mentioning a simple trick that's widely used.

Don't generate two random numbers per sample, and subtract them.

Instead, generate one random number per sample, and subtract the previous random number.

laugh.gif

Ouch, I'm stupid!! crying.gif 24 + 4 are only 28. I think I need some sleep... blink.gif

This post has been edited by madshi: Aug 28 2007, 14:48
Go to the top of the page
+Quote Post
SebastianG
post Aug 28 2007, 14:59
Post #46





Group: Developer
Posts: 1318
Joined: 20-March 04
From: Göttingen (DE)
Member No.: 12875



QUOTE (madshi @ Aug 28 2007, 15:50) *
P.S: The problem you have with my rand(16) is that the random range is too small, right? Wouldn't it be mathematically equivalent to do this?

Equivalent? No, this ditherer only generates 31 possible values.
But I suppose it's good enough.

Cheers!
SG
Go to the top of the page
+Quote Post
madshi
post Aug 28 2007, 16:23
Post #47





Group: Members
Posts: 16
Joined: 27-August 07
Member No.: 46548



QUOTE (SebastianG @ Aug 28 2007, 14:59) *
Equivalent? No, this ditherer only generates 31 possible values.
But I suppose it's good enough.

I don't understand why your solution is different mathematically.

CODE
Your original suggestion:
new_sample20 = ( (old_sample24 << 4) + rand(256) - rand(256) + 128 ) >> 8;

My modified suggestion:
new_sample20 = ( old_sample24 + ((rand(256) - rand(256)) >> 4) + 8 ) >> 4;


Now let me write them a bit differently:

CODE
Your original suggestion:
new_sample20 = ( ((old_sample24 << 4) >> 0) + (TPF(0x100) >> 0) + ((0x8 << 4) >> 0) ) >> 8;

My modified suggestion:
new_sample20 = ( ((old_sample24 << 4) >> 4) + (TPF(0x100) >> 4) + ((0x8 << 4) >> 4) ) >> 4;


Shouldn't that be mathematically identical?

In both your suggestion and my modified suggestion we have the three following values:

(1) "old_sample24 << 4" - bottom 4 bits are 0
(2) "TPF(0x100)" - bottom 4 bits contain data
(3) "0x8 << 4" - bottom 4 bits are 0

Of course I'm cutting off the bottom 4 bits of the TPF value before adding the three values, while you're doing the cutting off after the addition. But in the end IMO it doesn't matter because two of the three values have zeroed out bottom 4 bits. Only TPF has information in the bottom 4 bits. So those bottom 4 bits can never result in any other bits being impacted by "addition overflow". So basically the bottom 4 bits are useless and are being cut off by the final right shift, anyway. What am I missing?

Thanks much for your help!! smile.gif
Go to the top of the page
+Quote Post
kwwong
post Sep 4 2007, 02:59
Post #48





Group: Members
Posts: 113
Joined: 28-December 05
Member No.: 26686



QUOTE (2Bdecided @ Aug 28 2007, 08:18) *
It's probably worth mentioning a simple trick that's widely used.

Don't generate two random numbers per sample, and subtract them.

Instead, generate one random number per sample, and subtract the previous random number.

So

output = round(scale * input + this_random_number - previous_random_number)

This is still perfectly valid TPF dither, but has the effect of high pass filtering the dither, which is generally a desirable thing for audio (and many other applications).

Cheers,
David.


As I understand it that the random number generated is from a pseudo-random number generator function RAND(). I was wondering if it is necessary that the random source be white? In this case it make perfect sense that you can use the previous random number generated in the subtraction.

What is the effect of a non-white random source in dithering? blink.gif
Go to the top of the page
+Quote Post
SebastianG
post Sep 5 2007, 10:27
Post #49





Group: Developer
Posts: 1318
Joined: 20-March 04
From: Göttingen (DE)
Member No.: 12875



QUOTE (2Bdecided @ Aug 28 2007, 15:18) *
It's probably worth mentioning a simple trick that's widely used.
(...)
Instead, generate one random number per sample, and subtract the previous random number.
(...)
This is still perfectly valid TPF dither, but has the effect of high pass filtering the dither, which is generally a desirable thing for audio (and many other applications).

Honestly, I still need to wrap my head around this. Do you think that the quantization error's auto-correlation (the noise's colour) will be independent of the input-signal? I have my doubts but I'm not sure. huh.gif
The difference to "real noise shaping" is that this trick you mentioned kind of uses "filtering before quantization" whereas proper noise shaping operates on the quantized unfiltered noise which is guaranteed to be white due to "normal" dithering.

Cheers!
SG

This post has been edited by SebastianG: Sep 5 2007, 10:28
Go to the top of the page
+Quote Post
jlohl
post Sep 6 2007, 11:02
Post #50





Group: Members
Posts: 85
Joined: 5-November 05
Member No.: 25574



QUOTE
What is the effect of a non-white random source in dithering?

I did a small and free software to show/hear the effect of dither. The dither itself can be noise but also a sine wave. So you can try and listen to the result.
Get it here


--------------------
www.ohl.to
Go to the top of the page
+Quote Post

3 Pages V  < 1 2 3 >
Reply to this topicStart new topic
1 User(s) are reading this topic (1 Guests and 0 Anonymous Users)
0 Members:

 



RSS Lo-Fi Version Time is now: 21st November 2014 - 05:48