>>> 'cbā'.encode()
b'cb\xc4\x81'

But now the length of the byte-array is greater than the length of the string, which will mess up your padding. The simplest fix is to convert the string into an array of bytes, and then determine how much padding is required, and add that to the byte array.

>>> msg = 'cbā'
>>> msg_bytes = msg.encode()
>>> print(len(msg), len(msg_bytes), type(msg_bytes))
3 4 <class 'bytes'>

But note the length of the byte-array is (in this case) greater than the length of the string, which will mess up your padding. The simplest fix is to convert the string into an array of bytes, and then determine how much padding is required, and add that to the byte array.

>>> msg_bytes = msg.encode()
>>> payload_len = len(msg_bytes) + 1
>>> padding = -payload_len % frame_size
>>> frames = msg_bytes + b'=' * padding + bytes([padding + 1])

To reverse this in the decoding step:

>>> padding = frames[-1]            # amount of padding added
>>> msg_bytes = frames[:-padding]   # unpadded message bytes
>>> msg = msg_bytes.decode()        # decode bytes back to a string
>>> msg
'cbā'

def add_padding(s, i=128):
    padding = len(s) % i

    for j in range(i - padding):
        s += '='

    ...

If s is a 127 characters, padding becomes 127, but only 1 = character is added.

If s is 128 characters, padding becomes zero, which makes sense. But then 128 = characters get added to the string, which is really unexpected. I understand it is necessary, because you replace the last with the amount of padding, but it violates the principle of least surprise.

Using...

s += '=' * (i - padding)

would be more efficient than a loop.

Add Padding

def add_padding(s, i=128):
    padding = len(s) % i

    for j in range(i - padding):
        s += '='

    ...

If s is a 127 characters, padding becomes 127, but only 1 = character is added.

If s is 128 characters, padding becomes zero, which makes sense. But then 128 = characters get added to the string, which is really unexpected. I understand it is necessary, because you replace the last with the amount of padding, but it violates the principle of least surprise.

Using...

s += '=' * (i - padding)

would be more efficient than a loop.

After adding the padding, and converting it into bits, you remove the last 8 bits of the padding, replacing it with the length of the padding. You could have saved some work by not adding the extra padding character in the first place.

Here's some reworked code:

def add_padding(message, frame_size=128):
    payload_len = len(message) + 1        # Extra character encodes padding length
    padding = -payload_len % frame_size   # Amount of padding needed to fill frame

    frames = message + '=' * padding + chr(padding + 1)
    return ascii_to_bin(frames)

ASCII to Decimal

def ascii_to_decimal(string):
    # returns a list of ints
    return [ord(i) for i in string]

While this looks nice and simple, much of your code expects 8-bit bytes, not integers. The first ā in the string will get turned into a 257, and a subsequent bin(letter)[2:].zfill(length) will expand that to '100000001', despite being longer than 8 characters

Python has a builtin function which converts a string into an array of bytes. str.encode(). By default, it will use the UTF-8 encoding and will encode non-ASCII characters into multiple bytes, as required:

>>> 'cbā'.encode()
b'cb\xc4\x81'

But now the length of the byte-array is greater than the length of the string, which will mess up your padding. The simplest fix is to convert the string into an array of bytes, and then determine how much padding is required, and add that to the byte array.

As a bonus, the bytes (read-only) and bytearray (mutable) objects are way more efficient than using lists of integers, so you can gain some speed and/or memory efficiency by switching to them.