how to implement in matlab

n=1011(binary) 11 in decimal and b= 3(decimal) and finally getting answer as 011(binary). the b LSB of n to produce the subexponential code of n. How to implement it in matlab?

 n=1011  b=3  z=1|011  ans=011

Answer 1

[dpb]

Ohh....I think I finally figured out what want--the (variable) number of LSB(its) of the input value...ok, if interpretation is correct.

r=bitand(n, bin2dec(repmat('1',1,b)));  % value 

r=dec2bin(bitand(n, bin2dec(repmat('1',1,b))),b);  % bit representation

Use whatever integer is appropriate for the problem space; Matlab will work on default doubles if all are integers.

[Pooja]

Thank you so much sir.

[dpb]

No problem...wish there were a bitset() that takes a range and sets those in the variable but if there's a syntax that works I couldn't get it to do anything except return an array of individual bits in each element... :(

Hence the bin2dec and the string.

Could use arrayfun() and build a result to workaround that if wanted.

[Pooja]

Sir,do you know about split options in matlab.I am having two more problems.This is used in one decoding part.

First case is n=010011,k=3 i need to decode with k bits ie.3 bits. The theory is If the first bit is 0, the following k bits are the decoded value.

Second case is n=110011,i need to split the msb part upto the stopbit 0.This is the unary part(110) and also want to separate 011 as binary part(another part).

Thank you so much for your help.Could you please help me in this regard.

[dpb]

n=010011,k=3 i need to decode with k bits ie.3 bits. The theory is If the first bit is 0, the following k bits are the decoded value.

Me no follow...explain in more detail. Also, what in what form is 'n' -- internal storage of value, bit character string, ...?

On the latter, what's the precise definition of the stop bit? The first 0? That doesn't seem to make any sense if the result is to be '110'. And, can't hardly be the second consecutive if the latter three bits are all significant as '011'. Looks more like it's just a string of three (or k?) consecutive bits?

[Pooja]

This is used in decoding part of subexponential codes used for image compression.n is binary which is i/p binary stream,k be a parameter.There are two conditions for decoding n<2^k and n>=2^k.

if n>2^k for eg. n=110011,k=3 need to split the first part upto the stopbit 0.This is the unary part(110) and also want to separate 011 as binary part(another part). Stop bit is 0,the first 0 we see after 1,eg 110,0 is the stop bit.

After splitting we take the binary part and do bitor with 2^b ,where b we calculate by an equation.

Second case is n<2^k,here start bit will be 0. for eg.n=010011,k=3 i need to decode with k bits ie.3 bits needed to be taken as the decoded value.

My problem is to implement the first case and second case in matlab.I am copy pasting the C code of the decoding portion of subexponential coding.

if true
  % uintmax_t result =0;
// Subexponential has two different cases
if (( membuff -> GetBit ())==0){
// Case n <(2^ k)
return ( int ) membuff -> Get (k );
} else {
// Case n >(2^ k)
int b ,u;
uintmax_t base ;
// Count the number of 1' s until the stop bit .
u =1; // We already have read the first 1
while ( membuff - > GetBit ()){
u ++;
}
// Now the least b significant bits have to be read .
b=u +k -1;
base =1 < < b;
result = ( base | membuff - > Get (b ));
return ( int ) result ;
}
end

Thank you so much for helping me.

[dpb]

You still didn't answer precisely what form is the input you have -- is it a bitstream or an integer array of some size int or what? How to best proceed in Matlab depends on what you're starting with.

[Pooja]

its a bitstream.

[dpb]

Stored how in Matlab.

Man, this is like pulling teeth to get the least amount of info... :(

[Pooja]

This is used in decoding part of subexponential codes used for image compression.so the input coming is binary numbers.Which i have stored it as .txt file and i am calling that as the input.

[dpb]

Yes, ok, that's external storage, but how they're stored internal to Matlab is what is important to know how to try to process...

[Pooja]

As input we get binary i/ps .It is similar to that of other compression algorithm decoding.The input is binary data as shown in the example above.I am not able to write a program for the two cases mentioned above.Could you please help me.

[dpb]

But you still haven't answered the stinkin' question -- I don't care and it makes no difference about the background info, it's the detail of the data form itself that is needed.

HOW are you storing the data when you read it into Matlab? Is it a string of integers, characters, doubles, ...??? What and what sizes is the internal representation you're trying to operate on? And is this a fixed format or can the number of bits/integer (say, if it is integer) vary and so on and so on...iow a precise definition of the problem space.

[Pooja]

It is a string of integers.it is a 8 bit image 256*256 image.My problem is in the decoding part.

[dpb]

So, there's an array of uint8 which is to be decoded based on some k<n number of bits. Are these uint's in an array or individual? IOW, does it make any difference/help to operate on an array?

After that, let's get back to this thing about a "stop bit" and k and the value being > or < 2^k...so far, your description makes no sense.

Given the two examples you've shown before, they're BOTH > 2^k in the integer representation and if only deal w/ k bits, neither is.

>> uint8(bin2dec('110011'))
ans =
 51
>> uint8(bin2dec('010011'))
ans =
 19
>> uint8(bin2dec('110'))
ans =
  6
>> k=3;2^k
ans =
   8
>>

So, again, what part do this magic k and 2^k and start/stop bits play in the charade, precisely?

It would seem w/ only 3 bits one would have a lookup table solution in small amount of memory; give a table of possible inputs and desired outputs from it. Or, explain why simply decoding k bits doesn't work and an example of why it doesn't and what does in it's place.

[Pooja]

For eg.in the encoding part k=2 n=11 by equation

n>2^k.b(binary)=floor(log2(n))=floor(log2(11))=3=011

u(unary)=b-k+1=2 =110

final code = unary code+ b last bits on n(b=3 n=1011(binary of 11)) ans=110011(51 in decimal)

for decoding

ip= 110011

if the first bit is 1,count the no.of 1's until the stop bit(stop bit means 0) we get unary code(ie.u)

to get b, the least b significant bits have to be used ,ie. the b LSB have to be read,where b=u+k-1

The last step is to restore the original code by adding to 2^b the b LSB's

here i/p=110011,after doing this u=110 and b=011

final code=011+1000=1011. 1000 we get by 2^b . final code will be equal to n.Thus decoded

Above mentioned is the second case of n>2^k

first case is of n<2^k,in this case for decoding the i/p will be of like eg.011101.ie. the first bit is 0,the following k bits are the decoded value.

I have done the encoding part in matlab,but unable to do the decoding part for both the first and second case.The flow of decoding portion,the algorithm is clearly given in the above C code also.

Thank you.

[dpb]

n>2^k.
b = floor(log2(n)) = floor(log2(11)) = 3 = 011
u = b-k+1 = 3-2+1 = 2 --> 110  (????)

How do you get '110' from u=2???

As for the C code, it might be clear(er) if one had the header file. I presume there's a GetBit macro and there has to be a definition for the data type.

If it is clear to you, I suggest translating it directly; it isn't clear to me, at least w/o the missing pieces (but I'm no c-lizard).

for decoding

ip= 110011

if the first bit is 1,...

But in an 8-bit integer, there are 3 (unshown) leading zeros so how's one to know the "first" bit is the one?

... Above mentioned is the second case of n>2^k

And again we're back to how do you determine which group of bits to use?

i/p like 011101, the first bit is 0, ...

But how is there any indication in the input uint8 that the first bit isnt the '1' of the '11101' portion?

I can't see any unequivocal way to interpret an integer from the description. I'm sure there must be but there's something missing in the definition to remove that.

IOW, if one takes any input integer (other than identically 0) then there's always a leading 1 bit at some point. If you can't mask off k LSBs and use the rest, how does one decide?

Counting bits in a true bitstream would work (I think), but that's not what you're saying your input is (unless you've translated one into something else). I'm guessing that's what the C code macro(?) GetBit() must be doing is scanning the memory buffer but it's not possible to say for absolute certain (but it seems it must be else't afaict there is no unique solution).

So now we're back to the original problem/question -- what's the real datastream?

[Pooja]

unary coding is like that if it is 2 it will be like 110(two ones then one stop bit) if its 3 (1110).

My actual i/p is wavelet transformed DC coefficients,i am trying to write program with some egs.

The reference for the algorithm of subexponetial encoding and decoding is from the link http://upcommons.upc.edu/pfc/bitstream/2099.1/9926/1/PFC_Marcial_Clotet.pdf page 24(encoding) and 32(decoding).

Thank you

[dpb]

We're just going 'round in circles.

unary coding is like that if it is 2 it will be like 110(two ones then one stop bit) if its 3 (1110)

And there's the rub in decoding what you say your input is--an integer. One can't know a priori, what that length is w/o (afaict, anyway), starting from the beginning of a bitstream and decoding bit by bit.

Again, do you have the rest of the C code to disambiguate it?

It doesn't matter what the application is; if you have converted these coefficients into some integer array I think you've lost the ability to reconvert them--as you note the link there includes the word 'bitstream' -- that's significant to your problems.

You'll have to have some way to compact these coefficients into a bitstream or treat them as character strings of zeros and ones or some other way to disambiguate the start/stop of what is/isn't data. Within an integer of a fixed wordsize it's just not possible because the coding is of variable width and you can't discern what's leading data zero as opposed to not. (Or, if you can, I haven't yet been able to figure out how that would be)

[dpb]

do you have the rest of the C code to disambiguate it?

OK, I went to your link and I see that's where you got the code from--after reading it again, I'm now positive you have to create your input as a bitstream to be able to decode it--saving it as an integer array is worthless.

It falls back now onto your generation mechanism--once you figure that out and generate a useful data source, then we can talk about how to process it in Matlab.

And let's use your example above to illustrate why you have a problem--you say the coded value is to be 110011

>> ip=uint8(bin2dec('110011'));     % store as an uint8
>> dec2bin(ip,8)                    % display internal storage
ans =
00110011
>>

Now, we're supposed to read the first bit and decide based on whether it's set or not whether there's a u or this is it...but, unless the code width is always precisely 8 bits, the first bit is always going to be zero. There's simply no way to know which is actually the first bit in the code inside the integer not knowing a priori that the code is M bits--but your algorithm generates a variable-length code dependent on the magnitude of the value--Catch 22.

And, it's clear in reading the verbal description your reference gives in the steps to decode--

"[If] k is known, subexponential codes created following the directives specified ... can be decoded following these steps:

1. Read the first bit from the code.

2. If the first bit is 0, the following k bits are the decoded value. Otherwise, the unary code of u must be read.

It still would be a_good_thing (tm) if the missing header file(s)/functions/macros of the sample implementation were around somewhere--don't suppose you've any access to any of the author(s)? The paper at the link misses the header file with the specification of the assumed memory buffer structure and the macros(?) GetBit and Get that do the fetching therefrom.

[Pooja]

For an eg.If i/p is coming as 11000000,110000,110000 .

In matlab how to detect the first bit is 1 or 0.I mean to write the program whether the first bit of the i/p stream(lsb)is 1 0r 0?

[dpb]

As I've said all along, it all depends on the how the input "is coming". What is the storage mechanism of the values? If they're in an integer, the answer as above is "you can't" w/o some additional information as the leading bit will always be zero unless the code length exactly fills the width of the storage word (which it can't in general whatever the word length because the code length is variable). Again, I repeat, "Catch-22".

I spent a little time this morning reading the paper more thoroughly -- the giveaway is on p. 26, the middle paragraph below the numbered steps of how to generate the code. Note carefully the penultimate sentence of that paragraph which I quote --

"Finally, the length of the produced code must be computed in order to properly transfer the coded value to the next stage."

Unfortunately, the author didn't include the code or even a description of that "transfer to the next stage" mechanism although one can presume from the code of the subsequent decoder he built a memory buffer structure and overlaid a continuous bit stream into it w/ the aid of some unpublished helper functions/macros.

You've got to also do the same thing in your mechanism somehow; it's not possible to tell you the coding to do the decoding until you define what that storage transfer mechanism is going to be.

The obvious choices are to

a) build a bitstream as he apparently did, or

b) use a character or byte stream where each element represents a bit

c) use integer storage but pass a second vector of the same length that is the length of the corresponding code element.

The first is quite involved to implement as Matlab code as one doesn't have ready access to the low-level addressing while the latter two are pretty easy but have obvious performance and storage issues for anything other than demonstration purposes.

But, the problem is that you can't get there from here without one of the above or another equivalent way to be able to infer the code length in the decoder.

ADDENDUM:

Perhaps there's another way

d) Prepend a 'start' bit to the code in the integer coding--that would seem w/o a lot of thought given to contain enough information at minimal additional overhead/cost and not destroy the code.

ADDENDUM 2

e) IFF one can assure that the code length is always < word width, one could modify the coding slightly and eliminate the problem of the length. Since there's only a leading '0' for input n < (2^k), instead of coding it as b=0|u=n, store -n for those cases and use the subexponential coding only for n >= (2*k). Then you simply test for <0 and negate those cases in the decoder and use the algorithm for >=0.

[Pooja]

here the i/p is a bitstream.Encoding part it does a dwt,bit plane encoding,for ac coefficients and dc coefficients are seperately coded ,its o/p is given to the decoder.

[dpb]

All in all, I don't think you're either reading or comprehending what I've just spent a great deal of time and effort explaining and your repeating the same thing over and over doesn't help get us anywhere. :(

I understand that conceptually the coded values represent a bitstream. The problem is one of how are you storing these code values in Matlab and getting them to the desired decoder function?

Matlab doesn't have any such data structure as a "bitstream" -- it has various length integers, floats and higher-level abstractions built of the same.

And there's the problem--when you place the code value in one of those you've lost the implied length of the code irretrievably unless you've done something additional to allow it to be recovered.

Show a piece of Matlab coding that computes a coded value and then passes that value to the desired decoder.

You talk in words and give example values to decode but you don't provide the requested/needed information on how they are being manipulated in Matlab to have any way to know how to (or even for certain whether can) decode them in Matlab.

And, unless you use one of the previously-outlined alternatives or some other equivalent it can't be done in general from an integer representation. If you have somehow simulated a bitstream, then must have the details of that representation to know how to access it.

[Pooja]

I think i am not able to make out the question.I have stored the output of the encoded binary stream as save temp.txt .And for decoding i am calling as load temp.txt.

[dpb]

I think i am not able to make out the question...

Clearly. We've had this problem from the very first question that I can't seem to get across to you the difference between internal representation and the conceptualization of what that representation means.

And the underlying issue is that whatever bits you calculate if they're stored in anything except a sequence of only that number of bits are then irretrievable as to which are/aren't actually data in the larger entity when the code length they represent isn't a fixed length.

So, instead of trying to explain verbally show some source code. It will have a precise meaning in a common language...from that starting point maybe we can finally reach a mutual understanding.

Post your Matlab code that does the calculation of the coding and the write...it can be the few lines needed to read in or generate an input array, the call of the coder that returns the encoded result and the subsequent write/save to the file. That should be able to be brought down to a half-dozen lines or so at most I'd think.

Then, for completeness show the encoding routine and the line or two necessary to read the file. Wouldn't hurt to add the first few lines (3 or 4, say) of the file as well.

I'm pretty sure this will show that you're saving each encoded result in an array element, either an integer or default double, in which case you have the problem I've outlined above.

Do you understand the comment I made time stamped 11 Aug 2013 at 15:50? In particular, do you understand the implications of the sentence from the paper quoted there? If not, we've got a hurdle to get you over to see why there's a problem here.

I'll repeat it here for a reminder--

... p. 26, the middle paragraph below the numbered steps of how to generate the code. Note carefully the penultimate sentence of that paragraph--

"Finally, the length of the produced code must be computed in order to properly transfer the coded value to the next stage." (emphasis added)

It's that length that isn't available if the data are passed as individual array elements--then they're all the length of the (internal) storage unit and the length of the code stored in the array element is unknown. Hence we (as the decoder) don't know and can't tell which is the first encoded bit within all the bits of the array element.