8
\$\begingroup\$

I need to write a software in JAVA which allows me to simulate the transfer of some images over a noisy channel while adding redundancy with a repetition code . Before going into code details and issues, here are some requirements:

  • read files from a directory containing images
  • for each file, apply a repetition code (with n repetitions, user input)
  • for each file, send the result of the repetition code on a simulated channel with a given error probability. This means reading each bit and flipping it if we have an error
  • for each file, decode the file received from the channel and save it back as image

The parameters for the simulation are:

  • Files' folder
  • Number of repetitions
  • Error probability (as coefficient^exponent)
  • Output folder

I ended up organizing the project with these classes:

  • NoisyChannel - simulates the channel by reading a String of bits and applying the error based on some error model
  • SingleError - implements the single error model, meaning that we have a bit error if exponent times we generate a random number which is <=0.1
  • RepetitionCoder - applies the repetition code by taking the bit String, generating a char[stringLength*repetitions] array and filling it with the generated repetitions (010 with 3 repetitions will turn to 000111000)
  • RepetitionDecoder - decodes the bit String by splitting it every repetitions characters and applying a majority vote to each substring. The majority vote returns the most frequent character from the substring (001 will have 0 as result of the mjority vote)
  • Converter - utility class that contains methods to convert a byte[] to a bit String and the other way around

Now that you have a little bit of background, here's my problem: the simulation is really slow!

I've tried with 15 images with a size of 2.2MB each (so roughly 30MB of data) and 5 repetitions and it took around 8 minute to complete, which is way too high for me (running on an i5-4670 3.4GHz, 16GB 1333MHz dual-channel RAM, files stored on an USB3.0 external drive because I don't want to mess with my SSD)

This is why I need your help to try to speed things up.

TestLoop

for (int i = 0; i < 15; i++) {
    byte[] input = Files.readAllBytes(new File("D:\\testFrame.jpg").toPath());
    String inputString = Converter.byteArrayToBitString(input);
    int repetitions = 5, coefficient = 10, exponent = -3;
    // Repetitions (encoding)
    RepetitionCoder coder = RepetitionFactory.createRepetitionCoder(repetitions);
    String repCoderOutput = coder.encode(inputString);
    // Noisy channel
    BaseError error = ErrorFactory.createError(coefficient, exponent);
    NoisyChannel channel = new NoisyChannel(error);
    String channelOutput = channel.transfer(repCoderOutput);
    // Repetitions (decoding)
    RepetitionDecoder decoder = RepetitionFactory.createRepetitionDecoder(repetitions);
    String repDecoderOutput = decoder.decode(channelOutput);
    byte[] output = Converter.bitStringToByteArray(repDecoderOutput);
    Files.write(new File("D:\\testFrame_2.jpg").toPath(), output);
}

Converter.byteArrayToBitString

public static String byteArrayToBitString(byte[] source) {
    StringBuilder sb = new StringBuilder(8 * source.length);
    for (byte b : source) {
        sb.append(byteToBitString(b));
    }
    return sb.toString();
}

RepetitionCoder.encode

public String encode(String bitString){
    return repeat(bitString);
}

private String repeat(String bitString) {
    StringBuilder sb = new StringBuilder(bitString.length() * repetitions);
    for (char c : bitString.toCharArray()) {
        char[] chars = new char[repetitions];
        Arrays.fill(chars, c);
        sb.append(chars);
    }
    return sb.toString();
}

NoisyChannel.transfer

public String transfer(String input) {
    char[] bits = input.toCharArray();
    for (int i = 0; i < bits.length; i++) {
        bits[i] = errorModel.addError(bits[i]);
    }
    return new String(bits);
}

SingleError.addError

protected char addError(char source) {
    return (isError()) ? flipBit(source) : 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);
}

protected char flipBit(char bit) {
    return (bit == '0') ? (char) 49 : (char) 48;
}

RepetitionDecoder.decode

public String decode(String bitString) {
    String[] repetitionsString = splitStringEvery(bitString, repetitions);
    StringBuilder sb = new StringBuilder(repetitionsString.length);
    for (String rep : repetitionsString) {
        sb.append(majorityVote(rep));
    }
    return sb.toString();
}

private String[] splitStringEvery(String s, int interval) {
    int arrayLength = (int) Math.ceil(((s.length() / (double) interval)));
    String[] result = new String[arrayLength];

    int j = 0;
    int lastIndex = result.length - 1;
    for (int i = 0; i < lastIndex; i++) {
        result[i] = s.substring(j, j + interval);
        j += interval;
    }
    result[lastIndex] = s.substring(j);

    return result;
}

private char majorityVote(String buffer) {
    int zeroes = (int) buffer.chars().filter(b -> b == 48).count();
    return (zeroes > repetitions / 2) ? '0' : '1';
}

Converter.bitStringToByteArray

public static byte[] bitStringToByteArray(String string) {
    byte[] result = new byte[string.length() / 8];
    for (int i = 0; i < string.length(); i += 8) {
        String subString = string.substring(i, i + 8);
        result[i / 8] = bitStringToByte(subString);
    }
    return result;
}

Any idea on how to speed things up while keeping a good readability? Considered that I need to work with 500+ images, wasting 8 minutes every 15 images leads to huge times.

EDIT:

Created the follow-up question as suggested.

\$\endgroup\$
  • \$\begingroup\$ Hoy! You cannot edit your code in the question as this would invalidate existing answers. If you want us to review your new code, please post a follow up question! Thanks :) \$\endgroup\$ – IEatBagels Dec 16 '15 at 18:56
  • \$\begingroup\$ I thought that revision history was enough if somebody wanted to see the old code. How am I supposed to post a follow up question? Is it just a new question with maybe a link back here? \$\endgroup\$ – StepTNT Dec 16 '15 at 19:31
  • \$\begingroup\$ Exactly! And the edit history isn't there for this purpose. \$\endgroup\$ – IEatBagels Dec 16 '15 at 19:45
4
\$\begingroup\$

Using String is probably the main issue - you want to keep all data as bytes instead of converting it back and fort. Also, if you are only flipping bits and not dropping/adding them you might work directly on bytes: prepare a one byte mask ( from 8 calls to SingleError.isError()) for every byte of input and just XOR them.

\$\endgroup\$
  • \$\begingroup\$ Originally I used ByteArrayInputStream and ByteArrayOutputStream but I ended up having issues in the RepetitionCoder.decode method and I had to switch to String. Can you please expand your reply with some code? I've been working on this for the last 2 weeks and my head is hurting now :( \$\endgroup\$ – StepTNT Dec 15 '15 at 14:55
  • \$\begingroup\$ I forgot to add that the error is on bit level so I need to call isError 8 times for each byte. \$\endgroup\$ – StepTNT Dec 16 '15 at 10:18

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.