10
\$\begingroup\$

Following this question, I've tried to rewrite some core methods to avoid using String for bit operations, and I ended up using BitStream. The code is almost 8x faster than before but it still looks quite slow, because it processes 15 images per minute (0.25 FPS).

I think that there's still room for improvement but one of the requirements forces me to work at bit level, and probably Java is not the best choice when having to deal with bits.

I'm talking about the isError and addError methods, which need to be applied to each bit (basically the noisy channel is described by a bit-level error probability, meaning that each bit must be processed individually).

The BitStream class is from the org.icepdf.core.io package. Feel free to suggest a better alternative if you wish!

TestLoop

for (int i = 0; i < 15; i++) {
    byte[] input = Files.readAllBytes(new File("D:\\testFrame.jpg").toPath());
    ByteArrayInputStream bis = new ByteArrayInputStream(input);
    ByteArrayOutputStream bos = new ByteArrayOutputStream();
    // Repetition coder
    RepetitionCoder repCoder = RepetitionFactory.createRepetitionCoder(5);
    repCoder.encode(new BitStream(bis), new BitStream(bos));
    bis = new ByteArrayInputStream(bos.toByteArray());
    bos.reset();
    NoisyChannel channel = new NoisyChannel(ErrorFactory.createError(10, -3, 0));
    channel.transfer(new BitStream(bis), new BitStream(bos));
    bis = new ByteArrayInputStream(bos.toByteArray());
    bos.reset();
    // Repetition decoder
    RepetitionDecoder repDecoder = RepetitionFactory.createRepetitionDecoder(5);
    repDecoder.decode(new BitStream(bis), new BitStream(bos));
    // Write
    Files.write(outputFile.toPath(), bos.toByteArray());
}

RepetitionCoder.encode

public void encode(BitStream in, BitStream out) {
    try {
        while (in.available() > 0) {
            // Read one bit
            int currentBit = in.getBits(1);
            // Output that bit repetitions times
            for (int i = 0; i < repetitions; i++) {
                out.putBit(currentBit);
            }
        }
    } catch (IOException ex) {
        LOG.log(Level.SEVERE, ex.getMessage(), ex);
    }
}

NoisyChannel.transfer

public void transfer(BitStream input, BitStream output) throws IOException {
    while (input.available() > 0) {
        // Read one bit
        int bit = input.getBits(1);
        // Apply error
        int errorBit = errorModel.addError(bit);
        // Output the altered bit
        output.putBit(errorBit);
    }
}

SingleError.addError

protected int addError(int source) {
    if (isError()) {
        // Flip the bit
        return (source == 0) ? 1 : 0;
    }
    return source;
}

protected boolean isError() {
    for (int i = 0; i < Math.abs(exponent); i++) {
        if (Math.random() >= 0.1) {
            return false;
        }
    }
    return !(coefficient > 0 && Math.random() >= coefficient / 10);
}

RepetitionDecoder.decode

public void decode(BitStream in, BitStream out) throws IOException {
    while (in.available() > 0) {
        int zeroes = 0;
        // Read repetitions times and count zeroes
        for (int i = 0; i < repetitions; i++) {
            if (in.getBits(1) == 0) {
                zeroes += 1;
            }
        }
        // Output 0 if zeroes > repetitions/2, 1 otherwise
        out.putBit((zeroes > repetitions / 2) ? 0 : 1);
    }
}

Do you have any idea on this? I think that there may be a way of converting my code to work with byte instead of single bits but I'm not really that good with masks and bitwise operations.

EDIT: working with byte now.

SingleError.addError

protected boolean isError() {        
    return random.nextFloat() < errorProbability;
}

protected byte addError(byte source) {
    byte errorMask = 0;        
    for (int j = 0; j < 8; j++) {
        errorMask |= (isError()) ? 1 : 0;
        errorMask <<= 1;            
    }
    errorMask >>= 1;
    return (byte) (source ^ errorMask);
}

NoisyChannel.transfer

public void transfer(ByteArrayInputStream input, ByteArrayOutputStream output) throws IOException {
    while (input.available() > 0) {
        byte in = (byte) input.read();
        byte error = errorModel.addError(in);
        output.write(error);
    }
}
\$\endgroup\$
  • \$\begingroup\$ You're talking about 2MB images. That's 16 million bits to process. You repeat 5x, so output is 80 million bits. Per image. You operate bit wise, which results in several method calls per bit. That's many millions of method calls for each image. For this case, 4 seconds is pretty fast. \$\endgroup\$ – JimmyB Dec 18 '15 at 15:04
  • \$\begingroup\$ I have rolled back Rev 4, as the addError(byte) method that you added is inconsistent with NoisyChannel.transfer(), which calls addError(int). \$\endgroup\$ – 200_success Dec 20 '15 at 10:29
  • \$\begingroup\$ Please leave a comment before reverting so that I can fix it instead of rewriting :) I'm adding stuff here because I'll never have a final answer if I need to open a new question everytime I do a small update. \$\endgroup\$ – StepTNT Dec 20 '15 at 10:46
2
\$\begingroup\$

What's with isError()?

protected boolean isError() {
    for (int i = 0; i < Math.abs(exponent); i++) {
        if (Math.random() >= 0.1) {
            return false;
        }
    }
    return !(coefficient > 0 && Math.random() >= coefficient / 10);
}

It looks like you should be able to compute the bit error probability once, in the initialization. Then that whole method would become return Math.random() < effective_probability;.

You could also replace the use of Math.random() with your own, dedicated instance of java.util.Random and use its nextInt() for example, or nextFloat(). Either should be somewhat faster than the double-generating version.

Indeed, you can skip that boolean logic in favor of speedy bitwise xor, like

protected int getNoiseBit() {
  // Return 1 or 0.
}

protected int addError( final int input ) {
  return input ^ getNoiseBit();
}

Edit:

The xor approach naturally scales to multi-bit values, like:

// Generates 32 random bits (one int), of which each is 1 with p="probability"
protected int getErrorInt() {
  int bit = 1;
  int result = 0;

  for ( int i = 0; i < 32; i++ ) {
    if ( rng.nextFloat() < probability ) {
      result = result | bit;
    }
    bit = bit << 1;
  }

  return result;
}

// Accepts an int containing 1 to 32 bits of data and adds a probabilistic error.    
protected int addError( final int input ) {
  return input ^ getErrorInt();
}
\$\endgroup\$
  • \$\begingroup\$ I used Math.random() < errorProbability before, but somehow it generated a lot more errors than what it should (maybe Math.random() is biased somehow, because with errorProbability = 0.00001 isError() returned true 95% of the executions). I'm adding the new addError version because I've already moved to using a xor but it didn't help as much as I wanted. EDIT: I'm already computing the probability in the initialization as errorProbability = 10^exponent. Do you think that Random#nextFloat is faster thant Math#random? \$\endgroup\$ – StepTNT Dec 20 '15 at 10:03
  • \$\begingroup\$ Oh dear, Random#nextFloat is way faster than Math#random, gone from 945 kB/s to 1381 kB/s! Still I don't get how to make getNoiseBit without using the boolean logic tho :) \$\endgroup\$ – StepTNT Dec 20 '15 at 10:12
  • \$\begingroup\$ You could try something like final int threshold = Integer.MAX_INT * (1 - errorProbability) (initialize once!) and then int errorBit = (random.nextInt() & 0x7fffffff) / threshold; But it's probably not faster than the if (...) { return 1; } else { return 0; }. The latter will probably be optimized at runtime by the JVM, the former probably won't. \$\endgroup\$ – JimmyB Dec 20 '15 at 14:37
  • \$\begingroup\$ I'm accepting your answer because you provided good suggestions but the for in your edit will never exit because you wrote i-- instead of i++. \$\endgroup\$ – StepTNT Dec 20 '15 at 14:56
  • 1
    \$\begingroup\$ Oops. Well spotted :) Corrected it. - At first, I had i count down to 0 but I figured that the possible performance benefit (probably none after JVM optimization anyway) did not justify the less intuitive loop. \$\endgroup\$ – JimmyB Dec 20 '15 at 15:00
4
\$\begingroup\$

Let's look at the big picture (no pun intended). If your goal is to transmit an image file over a noisy channel, then the thing to optimize is not the implementation of the code. As long as your code is not egregiously bad, the thing to worry about is the efficiency of the protocol, because the data transmission should be much slower than the disk I/O, which in turn should be much slower than your what your CPU can handle.

Your idea for improving reliability is to transmit each bit r times consecutively. This scheme has several drawbacks:

  • It's inefficient. Obviously, r ≥ 2, which means that at the least, you double the transmission time. But doubling the data can only let the receiver detect that an error occurred. If you want to let the receiver automatically correct any detected errors without requesting retransmission, you need at least r ≥ 3, with r being odd, so that the receiver can go with a majority vote for each bit. Tripling or quintupling the transmission time is a very steep price to pay. (In your decoder, if r is even, then ties are biased towards 1, so you don't want to use even r.)
  • Transmitting each bit consecutively r times is akin to lowering the bit rate by a factor of r, which is the same simple trick that would normally be done by hardware. (Well, not exactly, since the clock speeds remain the same, and frame signalling mechanisms don't get slowed down.) For example, Ethernet and Wi-Fi can autonegotiate the speed down, or you can configure the speed manually.
  • If you transmit the image normally r times instead, then the same number of bits get transmitted, but the receiver might optimistically try to render the first full copy that it receives, then confirm and make corrections when it receives the subsequent copies. That could result in lower latency and a better user experience.
  • A single glitch in the analog medium is likely to wipe out multiple consecutive bits. If the bits were interleaved temporally, then you wouldn't be putting your eggs in the same basket.

So, what to do?

First of all, you should decide whether you are interested in error detection or error correction. Error detection means adding enough redundancy to let the receiver know that some error occurred; the receiver could either report the failure or request retransmission. Error correction means adding enough redundancy to let the receiver automatically correct errors, as long as there aren't too many errors.

A simple error detection mechanism is to add a parity bit. For example, you could transmit the data in groups of 7 bits, then insert an eighth bit such that the sum of all eight bits is even. (This is called "even parity"). That would let you detect up to 1 bit-flip in every 7 bits, at a cost of 14% overhead. You can tune the parameters as appropriate.

Another error detection mechanism is to transmit a checksum for the file, or maybe a checksum for every kibibyte of data. CRC is a common class of checksum algorithms, but you could also use something like SHA-2.

If you want an error-correcting code, then pick a scheme from the list. Reed Solomon error correction is a common scheme. You can tune the t parameter to tolerate whatever proportion of bit errors you expect to encounter, and still be able to completely reconstruct the data.

Keep in mind that low-level protocols, such as modems, Ethernet, IP, and TCP, generally have some crude checksum mechanism built-in already, so whatever you implement would be an additional layer of insurance.

\$\endgroup\$
  • \$\begingroup\$ While your post does completely make sense, what I'm doing is not my choice. I've been asked to implement a simulation with a repetition code, even if I know if it's quite inefficient. The issue here is that I quite don't understand why it's so slow because it does everything in memory and it works with 2MB images, which are not that big. \$\endgroup\$ – StepTNT Dec 18 '15 at 10:24
  • \$\begingroup\$ What exactly are the requirements of your assignment? If it's to implement a "repetition code", then as your linked Wikipedia article and I suggest, you should just transmit the file r times normally. The code would be so much simpler, and you wouldn't have to do any awkward bit-level manipulation. \$\endgroup\$ – 200_success Dec 18 '15 at 10:30
  • \$\begingroup\$ I need to implement a noisy channel with bit-level error, hence the awkward bit-level manipulation, and add a repetition code to deal with redundancy and error correction. The code needs to be like the one we saw in our class so I can't send the image multiple times but I actually have to repeat single bits. I wrote a version of addError that works with byte and masks, and I had a little boost but it still looks slow. \$\endgroup\$ – StepTNT Dec 18 '15 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.